【算法总结】图论-最短路径
一、概念
最短路径问题。即寻找图中某两个特定结点间最短的路径长度。所谓图上的路径，即从图中一个起始结点到一个终止结点途中经过的所有结点序列，路径的长度即所经过的边权和。
二、Floyd算法
用邻接矩阵保存原图，那么此时邻接矩阵中 edge[i][j]的值即表示从结点i到结点j，中间不经过任何结点时距离的最小值(若它们之间有多条边，取最小权值保存至邻接矩阵；也可能为无穷，即不可达)。假设结点编号为 1 到 N，我们再考虑从结点i到结点j中间只能经过编号小于等于1的结点（也可以不经过）时最短路径长度。与原始状况相比，在中间路径上可以经过的结点增加了编号为1 的结点。我们又知道，最短路径上的结点一定不会出现重复（不考虑存在负权值的情况）。那么，某两个结点间若由于允许经过结点 1 而出现了新的最短路径， 则该路径被结点 1 分割成两部分：由 i 到结点 1，同时中间路径上不经过结点 1 的第一段路径；由结点 1 到 j，中间路径上同样不经过结点 1 的第二段路径，其路径总长度为edge[i][1] + edge[1][j]。要确定该路径是否比不允许经过结点1时更短，我们比较edge[i][1] + edge[1][j]与edge[i][j]之间的大小关系。若前者较小， 则说明中间路径经过结点1时比原来更短，则用该值代表由i 到j 中间路径结点 编号小于等于1的最短路径长度；否则，该路径长度将依然保持原值edge[i][j]， 即虽然允许经过结点1，但是不经过时路径长度最短。
考虑更一般的情况，若edge[i][j]表示从结点i到结点j，中间只能经过编号小于k的点时的最短路径长度，我们可以由这些值确定当中间允许经过编号小于等 于k的结点时，它们之间的最短路径长度。同样，与原情况相比，新情况中允许出现在中间路径的结点新增了编号为 k 的结点，同理我们确定 edge[i][k] + edge[k][j]的值与edge[i][j]的值，若前者较小则该值代表了新情况中从结点i到结 点j的最短路径长度；否则，新情况中该路径长度依旧保持不变。
如上文所说，在图的邻接矩阵表示法中，edge[i][j]表示由结点i到结点j中间 不经过任何结点时的最短距离，那么我们依次为中间允许经过的结点添加结点 1、结点 2、……直到结点N，当添加完这些结点后，从结点i到结点j允许经过所有结点的最短路径长度就可以确定了，该长度即为原图上由结点 i 到结点 j 的 最短路径长度。
我们设ans[k][i][j]为从结点i到结点j允许经过编号小于等于k的结点时其最短路径长度。如上文，ans[0][i][j]即等于图的邻接矩阵表示中 edge[i][j]的值。我们通过如下循环，完成所有k对应的ans[k][i][j]值的求解：
for (int k = 1; k <= n; k++)//从1至n循环k { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++)//遍历所有的i，j { if (ans[k - 1][i][k] == 无穷 || anx[k - 1][k][j] == 无穷)//当允许经过前k-1个结点时，i，j不能与k联通，则ij之间目前为止不存在经过k的路径 { ans[k][i][j] = ans[k - 1][i][j];//保持原值，即从i到j经过前k个点和允许经过前k-1个结点时最短路径长度相同 continue; } if (ans[k - 1][i][j] == 无穷 || anx[k - 1][i][k] + ans[k - 1][k][j] < ans[k - 1][i][j])ans[k][i][j] = anx[k - 1][i][k] + ans[k - 1][k][j];//经过前k-1个结点，i,j不连通或者经过结点k可以得到更短的路径，则更新最短值 else ans[k][i][j] = ans[k - 1][i][j]; } } }
经过这样的n次循环后，我们即可得到所有结点间允许经过所有结点条件下的最短路径长度，该路径长度即为我们要求的最短路径长度。即若要求得 ab 之间的最短路径长度，其答案为ans[n][a][b]的值。
同时我们注意到，我们在通过ans[k - 1][i][j]的各值来递推求得ans[k][i][j]的值时，所有的ans[k][i][j]值将由ans[k - 1][i][j]和ans[k - 1][i][k] + ans[k - 1][k][j]的大小关系确定，但同时ans[k][i][k]和ans[k][k][j]必定与ans[k - 1][i][k]和ans[k - 1][k][j]的值相同，即这些值不会因为本次更新而发生改变。所以我们将如上代码片段简化成如下形式：
for (int k = 1; k <= n; k++)//从1至n循环k { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++)//遍历所有的i，j { if (ans[i][k] == 无穷 || anx[k][j] == 无穷)continue; if (ans[i][j] == 无穷 || anx[i][k] + ans[k][j] < ans[i][j])ans[i][j] = anx[i][k] + ans[k][j]; } } }
如该代码片段所示，我们将原本的三维数组简化为二维数组，而每次更新时直接在该二维数组上进行更新。这是有原因的，当最外层循环由k - 1变为k时， 各 ans[i][k]和 ans[k][j]的值不会因为本次更新发生改变（当前 i 到 k 的最短路径中途必不经过结点k），而本次更新又是由它们的值和各ans[i][j]的值比较而进行 的。所以我们直接在二维数组上进行本次更新，并不会影响到本次更新中其它各值的判定。节省了大量的内存空间，同时还省略了保持原值的操作。
例 5.5 最短路
解题思路
本例是最简单的最短路问题了。我们首先分析复杂度，如我们在上文中给出的代码所示，floyd算法主要包括一个三重循环，每重循环的循环次数均是N，这样 Floyd算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)，其中N均为图中结点的个数。
在本例中N最大值为100，N^3的时间复杂度尚在我们可以接受的范围内。
AC代码
#include<cstdio> int ans[101][101];//二维数组，其初始值即为该图的邻接矩阵 int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0)break; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { ans[i][j] = -1;//初始化邻接矩阵，用-1代表无穷 } ans[i][i] = 0;//初始化，自己到自己的路径长度为0 } while (m--)//读入道路 { int a, b, c; scanf("%d%d%d", &a, &b, &c); ans[a][b] = ans[b][a] = c;//无向图，赋值两次 } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (ans[i][k] == -1 || ans[k][j] == -1)continue; if (ans[i][j] == -1 || ans[i][k] + ans[k][j] < ans[i][j])ans[i][j] = ans[i][k] + ans[k][j]; } } } printf("%d ", ans[1][n]); } return 0; }
Floyd算法特点总结：
- 牢记其时间复杂度为O(N^3)，所以在大部分机试题的时间允许范围内，它要求被求解图的大小不大于200个结点（此时时间复杂度为800万），若超过该数字该算法很可能因为效率不够高而被判超时。
- Floyd 算法利用一个二维矩阵来进行相关运算，所以当图使用邻接矩阵表示时更为方便。若原图并非由邻接矩阵给出时我们设法将其转换，注意当两个结点间有多余一条边时，我们选择长度最小的边权值存入邻接矩阵。
- 当Floyd算法完成后，图中所有结点之间的最短路都将被确定。所以，其较适用于要求询问多个结点对之间的最短路径长度问题，即全源最短路问题。
三、Dijkstra算法
它与之前讨论的Floyd算法有一个非常明显的区别，Floyd 算法可以计算出图上所有结点对之间的最短路径长度，Dijkstra 算法只能求得某特定结点到其它所有结点的最短路径长度，即单源最短路路径问题。
那么该如何确定某特定结点到其它所有结点的最短距离呢？我们将按照最短路径长度递增的顺序确定每一个结点的最短路径长度，即先确定的结点的最短路径长度不大于后确定的结点的最短路径长度。这样有一个好处，当确定一个结点的最短路径长度时，该最短路径上所有中间结点的最短路径长度必然已经被确定了（中间路径的最短路径长度必小于这个结点的最短路径长度）。不妨设有结点 1到N，我们将要求从结点1出发到其它所有结点的最短路径长度。初始时，设结点 1 到其它所有点的最短路径长度均为无穷（或不确定的），我们立即确定由结点1到结点1的最短路径长度距离为0。设已经确定最短路径长度的结点集合为集合 K，于是我们将结点 1 加入该集合。将问题一般化，假设集合 K 中已经保存了最短路径长度最短的前m个结点，它们是P1，P2……Pm，并已经得出它们的最短路径长度。那么第 m+1 近的结点与结点 1 的最短路径上的中间结点一定全部属于集合 K，这是因为若最短路径上中间有一个不属于集合 K 的结点， 则它的最短路径距离一定小于第 m+1 近的结点的最短路径长度，与距离小于第 m+1 近的结点的最短路径已经全部确定、这样的结点全部属于集合 K 矛盾。那么第 m+1 近结点的最短路径必是由以下两部分组成，从结点 1 出发经由已经确定的最短路径到达集合K中的某结点P2，再由P2经过一条边到达该结点。为此，我们遍历与集合K中结点直接相邻的边，设其为（U，V，C)，其中 U属于集合 K，V不属于集合K，计算由结点1出发经过已经确定的最短路到达结点U，再由结点U经过该边到达结点V的路径长度。该路径长度为已经确定的结点U的最短路径长度+C。所有与集合K直接相邻的非集合K结点中，该路径长度最短的那个结点即确定为第 m+1 近结点，并将该点假如集合 K。如此往复，直到结点1到所有结点的最短路径全部确定。
算法流程：
1.初始化，集合 K 中加入结点 1，结点 1 到结点 1 最短距离为 0，到其它结点为无穷（或不确定）。
2.遍历与集合 K 中结点直接相邻的边（U，V，C），其中 U 属于集合 K，V 不属于集合 K，计算由结点 1 出发按照已经得到的最短路到达 U，再由 U 经过该边到达V时的路径长度。比较所有与集合K中结点直接相邻的非集合K结点的路径长度，其中路径长度最小的结点被确定为下一个最短路径确定的结点，其最短路径长度即为这个路径长度，最后将该结点加入集合K。
3.若集合K中已经包含了所有的点，算法结束；否则重复步骤2。
例 5.5 最短路
用Dijkstra算法的AC代码
#include<cstdio> #include<vector> using namespace std; struct E//邻接链表中的链表元素结构体 { int next;//代表直接相邻的结点 int c;//代表该边的权值 }; vector<E> edge[101];//邻接链表 bool mark[101];//标记，当mark[j]为true时表示结点j的最短路径长度已经得到，该结点已经加入集合K int Dis[101];//距离向量，当mark[i]为true时，表示已得的最短路径长度，否则，表示所有从结点1出发，经过已知的最短路径达到集合K中的某结点，再经过一条边到达结点i的路径中最短的距离 int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0)break; for (int i = 1; i <= n; i++)edge[i].clear();//初始化邻接链表 while (m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); E tmp; tmp.c = c; tmp.next = b; edge[a].push_back(tmp); tmp.next = a; edge[b].push_back(tmp);//将邻接信息加入邻接链表，无向图，边的信息分别加入两个顶点 } for (int i = 1; i <= n; i++)//初始化 { Dis[i] = -1;//所有距离为-1，即不可达 mark[i] = false;//所有结点不属于集合K } Dis[1] = 0;//得到最近的点为结点1，长度为0 mark[1] = true;//将结点1加入集合K int newP = 1;//集合K中新加入的点为结点1 for (int i = 1; i < n; i++)//循环n-1次，按照最短路径递增的顺序确定其他n-1个点的最短路径长度 { for (int j = 0; j < edge[newP].size(); j++)//遍历与新加入集合K中的结点直接相邻的边 { int t = edge[newP][j].next;//该边的另一个结点 int c = edge[newP][j].c;//该边的长度 if (mark[t] == true)continue;//已加入集合K if (Dis[t] == -1 || Dis[t] > Dis[newP] + c)Dis[t] = Dis[newP] + c;//该点不可达或者从newP到达该点更近，则更新最短距离 } int min = 123123123;//最小值初始化为一个大数 for (int j = 1; j <= n; j++)//遍历所有结点 { if (mark[j] == true)continue;//属于集合K则跳过 if (Dis[j] == -1)continue;//该结点不可达，跳过 if (Dis[j] < min)//若该结点是没加入的结点中目前最短的 { min = Dis[j];//更新其为最小值 newP = j;//新加入的点暂定为该点 } } mark[newP] = true;//新加入的点加入集合K } printf("%d ", Dis[n]);//输出 } return 0; }
该代码中，使用了邻接链表保存图信息。由此可见，Dijstra 算法很好的支持邻接链表，但同时它也可以被应用于邻接矩阵。这里使用邻接链表，是为了方便读者更详细的了解用vector模拟邻接链表的方法。
例 5.6 最短路径问题
解题思路
在该例中，我们不仅需要求得起点到终点的最短距离，还需要在有多条最短路径的时，选取花费最少的那一条。要解决这个问题，我们只要更改Dijstra 算 法中关于“更近”的评判标准即可：有两条路径，若它们距离不一样时，距离小的更近；若距离一样时花费少的更近。当定义这种新的评判标准后，Dijstra算法照样能为我们求得“最近”的路径长度。
Dijkstra算法AC代码
#include<cstdio> #include<vector> using namespace std; struct E//邻接链表中的链表元素结构体 { int next;//代表直接相邻的结点 int c;//代表该边的权值 int cost; }; vector<E> edge[1001];//邻接链表 int cost[1001];//花费数组 bool mark[1001];//标记，当mark[j]为true时表示结点j的最短路径长度已经得到，该结点已经加入集合K int Dis[1001];//距离向量，当mark[i]为true时，表示已得的最短路径长度，否则，表示所有从结点1出发，经过已知的最短路径达到集合K中的某结点，再经过一条边到达结点i的路径中最短的距离 int main() { int n, m; int S, T;//起点和终点 while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0)break; for (int i = 1; i <= n; i++)edge[i].clear();//初始化邻接链表 while (m--) { int a, b, c, cost; scanf("%d%d%d%d", &a, &b, &c, &cost); E tmp; tmp.c = c; tmp.cost = cost; tmp.next = b; edge[a].push_back(tmp); tmp.next = a; edge[b].push_back(tmp);//将邻接信息加入邻接链表，无向图，边的信息分别加入两个顶点 } scanf("%d%d", &S, &T);//读入起点和终点信息 for (int i = 1; i <= n; i++)//初始化 { Dis[i] = -1;//所有距离为-1，即不可达 mark[i] = false;//所有结点不属于集合K } Dis[S] = 0;//得到最近的点为结点S，长度为0 mark[S] = true;//将结点S加入集合K int newP = S;//集合K中新加入的点为结点S for (int i = 1; i < n; i++)//循环n-1次，按照最短路径递增的顺序确定其他n-1个点的最短路径长度 { for (int j = 0; j < edge[newP].size(); j++)//遍历与新加入集合K中的结点直接相邻的边 { int t = edge[newP][j].next;//该边的另一个结点 int c = edge[newP][j].c;//该边的长度 int co = edge[newP][j].cost;//花费 if (mark[t] == true)continue;//已加入集合K if (Dis[t] == -1 || Dis[t] > Dis[newP] + c || Dis[t] == Dis[newP] + c && cost[t] > cost[newP] + co) { Dis[t] = Dis[newP] + c;//该点不可达或者从newP到达该点更近，则更新最短距离 cost[t] = cost[newP] + co;//更新花费 } } int min = 123123123;//最小值初始化为一个大数 for (int j = 1; j <= n; j++)//遍历所有结点 { if (mark[j] == true)continue;//属于集合K则跳过 if (Dis[j] == -1)continue;//该结点不可达，跳过 if (Dis[j] < min)//若该结点是没加入的结点中目前最短的 { min = Dis[j];//更新其为最小值 newP = j;//新加入的点暂定为该点 } } mark[newP] = true;//新加入的点加入集合K } printf("%d %d ", Dis[T], cost[T]);//输出 } return 0; }
值得一提的是，若由结点U到结点V的最短路径不存在，即他们不连通，那 么当Dijstra算法完成以后，V结点仍然不属于集合K。即当完成Dijstra算法后， mark[V]依然为 false 即说明，结点 U 到结点 V 的最短路不存在。
Dijkstra算法特点总结：
时间复杂度为 O(N^2)（若在查找最小值处利用堆进行优化，则时间复杂度可以降到O(N*logN)，N为结点的个数。空间复杂度为O(N）（不包括保存图所需的空间）。它同时适用于邻接矩阵和邻接链表形式保存的有向图和无向图。它求解从某一个特定的起点出发，到 其它所有点的最短路径，即单源最短路径问题。