第4章 第3 4节 图论算法(C++版).pdf

第四章 第三节 最短路径算法 如下图所示我们把边带有权值的图称为带权图边的权值可以理 解为两点之间的距离一张图中任意两点间会有不同的路径相连最短 路径就是指连接两点的这些路径中最短的一条 我们有四种算法可以有效地解决最短路径问题有一点需要读者特 别注意边的权值可以为负当出现负边权时有些算法不适用 一求出最短路径的长度 以下没有特别说明的话dis[u][v]表示从u v最短路径长度w[u][v]表