数据结构与算法-图论(三)-最短路径
在讨论完最小生成树后，我们再来了解图论中另一个经典问题：最短路径问题。即寻找图中某两个特定结点间最短的路径长度。所谓图上的路径，即从图中一个起始终点到一个终止终点途中经过的所有结点序列，路径的长度即所经过的边权和。
最短路径问题在实际中的应用也非常广泛，例如确定某两个城市间的最短行车路线长度。要解决这类问题，我们要根据图的特点和问题的特征选择不同的算法。
我们首先来介绍第一种计算最短路径长度的算法-Floyd算法
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。
题目描述：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，非常累！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
输入：
输入包括多组数据。每组数据第一行是两个整数N,M(N <= 100,M <= 10000),N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A,B,C(1 <= A,B <= N, 1 <= C <= 1000),表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。当输入为两个0时，输入结束。
输出：
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。
样例输入：
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
样例输出：
3
2
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
#define 101 N
int ans[N][N];
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; // 若两值中有一个值为无穷，则ans[i][j]不能由于经过结点k而被更新，跳过循环，保持原值
if(ans[i][j] == -1 || ans[i][k] + ans[k][j] < ans[i][j])
ans[i][j] = ans[i][k] + ans[k][j];
// 当由于进过k可以获得更短的最短路径时，更新该值
}
}
}
printf("%d\n",ans[1][n]); // 循环结束后输出答案
}
return 0;
}
运行结果：
对于Floyd算法具体理解可以参考这篇博客：https://www.cnblogs.com/wangyuliang/p/9216365.html
我们总结Floyd算法的特点。第一，牢记其时间复杂度为O(N^3),所以在大部分机试题的时间允许范围内，他要求被求解图的大小不大于200个结点，若超过该数字该算法很可能因为效率不够高而被判超时。第二，Floyd算法利用一个二维矩阵来进行相关运算，所以当图使用邻接矩阵表示时更为方便。若原图并非由邻接矩阵给出时我们设法将其转换，注意当两个节点间有多余一条边时，选择长度最小的边权值存入邻接矩阵。第三，当Floyd算法完成后，图中所有结点之间的最短路径都将被确定。所以，其较适用于要求询问多个结点对之间的最短路径长度问题，即全源最短路径问题。了解它的这些特点，将有利于我们在特定问题中决定是否使用Floyd算法。
在讨论完Floyd算法后，我们来看另一种与其特点完全不同的最短路径算法-Dijkstra算法(迪杰斯特拉算法)。它与之间讨论的Floyd算法有一个非常明显的区别，Floyd算法可以计算出图中所有结点对之间的最短路径长度，Dijkstra算法只能求得某特定结点到其他所有结点的最短路径长度，即单源最短路径问题。
关于Dijstra算法的具体理解可以参考这篇博客：https://www.cnblogs.com/wangyuliang/p/9216511.html
我们使用Dijstra算法重写上例：
#include <iostream>
#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中的某结点
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++){
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;
}
int min = 123123123; // 最小值初始化为一个大整数，为找最小值做准备
for(int j = 1 ; j <= n ; j++){// 遍历所有结点
if(mark[j] == true) continue;
if(Dis[j] == -1) continue;
if(Dis[j] < min){
min = Dis[j];
newP = j; // 新加入的点暂定为该点
}
}
mark[newP] = true;
}
printf("%d\n",Dis[n]);
}
}
运行结果：
如代码所示，我们用mark[i]的值来确定结点i的最短路径是否已经被确定，并根据结点i是否属于集合K,Dis[i]中的数字体现出不同的意义。当结点i属于集合K时，Dis[i]代表结点i已经被确定的最短路径长度；相反，若结点i不属于集合K,那么Dis[i]表示，所有从结点1出发先按照某条最短路径到达已经在集合K中的结点，并由该结点经过一条边到达结点i路径中的最短距离。
总之就是将新加入进K集合的点的所有出边进行“松弛”，然后在“松弛”完后的非K集合中寻找距离最小的点加入集合K,并将新加入的点标记。
我们再来看一个例题：
题目描述：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t,要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入：
输入n,m,点的编号是1~n，然后m行，每行4个数a,b,d,p,表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数s,t;起点s，终点t。n和m为0时输入结束。
输出：
输出一行有两个数：最短距离及其花费。
样例输入：
3 2
1 2 5 6
2 3 4 5
1 3
0 0
样例输出：
9 11
在该例中，我们不仅需要求得起点到终点的最短距离，还需要在有多条最短路径时，选取花费最少的那一条。要解决这个问题，只要更改Dijstra算法中关于“更近”的评判标准即可：有两条路径，若他们距离不一样时，距离小的更近；若距离一样时花费少的更近。当定义这种新的评判标准后，Dijstra算法照样能为我们求得“最近”的路径长度。
代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct E{// 邻接链表元素结构体
int next;
int c;
int cost;
};
vector<E> edge[1001]; // 邻接链表
int Dis[1001]; // 距离数组
int cost[1001]; // 花费数组
bool mark[1001]; // 是否属于集合K数组
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;
mark[i] = false;
}
Dis[S] = 0;
mark[S] = true;
int newP = S; // 起点为S,将其加入集合K,且其最短距离确定为0
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < edge[newP].size(); j++){
int t = edge[newP][j].next;
int c = edge[newP][j].c;
int co = edge[newP][j].cost; // 花费
if(mark[t] == true) continue;
if(Dis[t] == -1 || Dis[t] > Dis[newP] + c || Dis[t] == Dis[newP] + c && cost[t] > cost[newP]+co){
Dis[t] = Dis[newP] + c;
cost[t] = cost[newP] + co;
}
}
int min = 123123123;
for(int j = 1 ; j <= n ; j++){
if(mark[j] == true) continue;
if(Dis[j] == -1) continue;
if(Dis[j] < min){
min = Dis[j];
newP = j;
}
}
mark[newP] = true;
}
printf("%d %d\n",Dis[T],cost[T]); // 输出答案
}
return 0;
}
运行结果：
