数据结构 第15讲 一场说走就走的旅行——最短路径
一场说走就走的旅行——最短路径
本内容来源于《趣学算法》，在线章节：http://www.epubit.com.cn/book/details/4825
有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
“哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太out了，学计算机的最短路线你用手算？”
暴汗……，“小子你别牛，你知道怎么算？”
“呃，好像是叫什么迪科斯彻的人会算。”
哈哈，关键时刻还要老妈上场了！
图2-8 一场说走就走的旅行
2.5.1 问题分析
根据题目描述可知，这是一个求单源最短路径的问题。给定有向带权图G =（V，Ｅ），其中每条边的权是非负实数。此外，给定V中的一个顶点，称为源点。现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
如何求源点到其他各点的最短路径呢？
如图2-9所示，艾兹格•W•迪科斯彻（Edsger Wybe Dijkstra），荷兰人，计算机科学家。他早年钻研物理及数学，后转而研究计算学。他曾在1972年获得过素有“计算机科学界的诺贝尔奖”之称的图灵奖，与Donald Ervin Knuth并称为我们这个时代最伟大的计算机科学家。
图2-9 艾兹格•W•迪科斯彻
2.5.2 算法设计
Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V−S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V−S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V−S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V−S中的顶点加入到集合S中，同时更新数组dist[]。一旦S包含了所有顶点，dist[]就是从源到所有其他顶点之间的最短路径长度。
（1）数据结构。设置地图的带权邻接矩阵为map[][]，即如果从源点u到顶点i有边，就令 map[u][i]等于<u，i>的权值，否则 map[u][i]=∞（无穷大）；采用一维数组 dist[i]来记录从源点到i顶点的最短路径长度；采用一维数组p[i]来记录最短路径上i顶点的前驱。
（2）初始化。令集合S={u}，对于集合V−S中的所有顶点x，初始化dist[i]=map[u][i]，如果源点u到顶点i有边相连，初始化p[i]=u，否则p[i]= −1。
（3）找最小。在集合V−S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即dist[t]=min（dist[j]|j属于V−S集合），则顶点t就是集合V−S中距离源点u最近的顶点。
（4）加入S战队。将顶点t加入集合S中，同时更新V−S。
（5）判结束。如果集合V−S为空，算法结束，否则转（6）。
（6）借东风。在（3）中已经找到了源点到t的最短路径，那么对集合V−S中所有与顶点t相邻的顶点j，都可以借助t走捷径。如果dis[j]>dist[t]+map[t][j]，则dist[j]=dist[t]+map[t][j]，记录顶点j的前驱为t，有p[j]= t，转（3）。
由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过数组p[]逆向找到最短路径上经过的城市。
2.5.3 完美图解
现在我们有一个景点地图，如图2-10所示，假设从1号结点出发，求到其他各个结点的最短路径。
图2-10 景点地图
算法步骤如下。
（1）数据结构
设置地图的带权邻接矩阵为map[][]，即如果从顶点i到顶点j有边，则map[i][j]等于<i，j>的权值，否则map[i][j]=∞（无穷大），如图2-11所示。
图2-11 邻接矩阵map[][]
（2）初始化
令集合S={1}，V−S={2，3，4，5}，对于集合V−S中的所有顶点x，初始化最短距离数组dist[i]=map[1][i]，dist[u]=0，如图2-12所示。如果源点1到顶点i有边相连，初始化前驱数组p[i]=1，否则p[i]= −1，如图2-13所示。
图2-12 最短距离数组dist[]
图2-13 前驱数组p[]
（3）找最小
在集合V−S={2，3，4，5}中，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-14所示。
图2-14 最短距离数组dist[]
找到最小值为2，对应的结点t=2。
（4）加入S战队
将顶点t=2加入集合S中S={1，2}，同时更新V−S={3，4，5}，如图2-15所示。
图2-15 景点地图
（5）借东风
刚刚找到了源点到t=2的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵都可以看出，2号结点的邻接点是3和4号结点，如图2-16所示。
图2-16 邻接矩阵map[][]
先看3号结点能否借助2号走捷径：dist[2]+map[2][3]=2+2=4，而当前dist[3]=5>4，因此可以走捷径即2—3，更新dist[3]=4，记录顶点3的前驱为2，即p[3]= 2。
再看4号结点能否借助2号走捷径：如果dist[2]+map[2][4]=2+6=8，而当前dist[4]=∞>8，因此可以走捷径即2—4，更新dist[4]=8，记录顶点4的前驱为2，即p[4]= 2。
更新后如图2-17和图2-18所示。
图2-17 最短距离数组dist[]
图2-18 前驱数组p[]
（6）找最小
在集合V−S={3，4，5}中，依照贪心策略来寻找dist[]具有最小值的顶点t，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-19所示。
图2-19 最短距离数组dist[]
找到最小值为4，对应的结点t=3。
（7）加入S战队
将顶点t=3加入集合S中S={1，2，3}，同时更新V−S={4，5}，如图2-20所示。
图2-20 景点地图
（8）借东风
刚刚找到了源点到t =3的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵可以看出，3号结点的邻接点是4和5号结点。
先看4号结点能否借助3号走捷径：dist[3]+map[3][4]=4+7=11，而当前dist[4]=8<11，比当前路径还长，因此不更新。
再看5号结点能否借助3号走捷径：dist[3]+map[3][5]=4+1=5，而当前dist[5]=∞>5，因此可以走捷径即3—5，更新dist[5]=5，记录顶点5的前驱为3，即p[5]=3。
更新后如图2-21和图2-22所示。
图2-21 最短距离数组dist[]
图2-22 前驱数组p[]
（9）找最小
在集合V−S={4，5}中，依照贪心策略来寻找V−S集合中dist[]最小的顶点t，如图2-23所示。
图2-23 最短距离数组dist[]
找到最小值为5，对应的结点t=5。
（10）加入S战队
将顶点t=5加入集合S中S={1，2，3，5}，同时更新V−S={4}，如图2-24所示。
图2-24 景点地图
（11）借东风
刚刚找到了源点到t =5的最短路径，那么对集合V−S中所有t的邻接点j，都可以借助t走捷径。我们从图或邻接矩阵可以看出，5号结点没有邻接点，因此不更新，如图2-25和图2-26所示。
图2-25 最短距离数组dist[]
图2-26 前驱数组p[]
（12）找最小
在集合V−S={4}中，依照贪心策略来寻找dist[]最小的顶点t，只有一个顶点，所以很容易找到，如图2-27所示。
图2-27 最短距离数组dist[]
找到最小值为8，对应的结点t=4。
（13）加入S战队
将顶点t加入集合S中S={1，2，3，5，4}，同时更新V−S={ }，如图2-28所示。
图2-28 景点地图
（14）算法结束
V−S={ }为空时，算法停止。
由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，也可通过前驱数组p[]逆向找到最短路径上经过的城市，如图2-29所示。
图2-29 前驱数组p[]
例如，p[5]=3，即5的前驱是3；p[3]=2，即3的前驱是2；p[2]=1，即2的前驱是1；p[1]= −1，1没有前驱，那么从源点1到5的最短路径为1—2—3—5。
2.5.4 伪代码详解
（1）数据结构
n：城市顶点个数。m：城市间路线的条数。map[][]：地图对应的带权邻接矩阵。dist[]：记录源点u到某顶点的最短路径长度。p[]：记录源点到某顶点的最短路径上的该顶点的前一个顶点（前驱）。flag[]：flag[i]等于true，说明顶点i已经加入到集合S，否则顶点i属于集合V−S。
const int N = 100; //初始化城市的个数，可修改
const int INF = 1e7; //无穷大
int map[N][N],dist[N],p[N],n,m;
bool flag[N];（2）初始化源点u到其他各个顶点的最短路径长度，初始化源点u出边邻接点（t的出边相关联的顶点）的前驱为u：
bool flag[n];//如果flag[i]等于true，说明顶点i已经加入到集合S;否则i属于集合V-S
for(int i = 1; i <= n; i ++)
{
dist[i] = map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
flag[i]=false;
if(dist[i]==INF)
p[i]=-1; //说明源点u到顶点i无边相连，设置p[i]=-1
else
p[i]=u; //说明源点u到顶点i有边相连，设置p[i]=u
}（3）初始化集合S，令集合S={u}，从源点到u的最短路径为0。
flag[u]=true; //初始化集合S中，只有一个元素：源点 u
dist[u] = 0; //初始化源点 u的最短路径为0，自己到自己的最短路径（4）找最小
在集合V−S中寻找距离源点u最近的顶点t，若找不到t，则跳出循环；否则，将t加入集合S。
int temp = INF,t = u ;
for(int j = 1 ; j <= n ; j ++) //在集合V-S中寻找距离源点u最近的顶点t
if( !flag[j] && dist[j] < temp)
{
t=j; //记录距离源点u最近的顶点
temp=dist[j];
}
if(t == u) return ; //找不到t，跳出循环
flag[t] = true; //否则，将t加入集合S（5）借东风
考查集合V−S中源点u到t的邻接点j的距离，如果源点u经过t到达j的路径更短，则更新dist[j] =dist[t]+map[t][j]，即松弛操作，并记录j的前驱为t：
for(int j = 1; j <= n; j ++) //更新集合V-S中与t邻接的顶点到源点u的距离
if(!flag[j] && map[t][j]<INF) //!flag[j]表示j在V-S中，map[t][j]<INF表示t与j邻接
if(dist[j]>(dist[t]+map[t][j])) //经过t到达j的路径更短
{
dist[j]=dist[t]+map[t][j] ;
p[j]=t; //记录j的前驱为t
}重复（4）～（5），直到源点u到所有顶点的最短路径被找到。
2.5.5 实战演练
//program 2-4
#include <cstdio>
#include <iostream>
#include<cstring>
#include<windows.h>
#include<stack>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 初始化无穷大为10000000
int map[N][N],dist[N],p[N],n,m;//n城市的个数，m为城市间路线的条数
bool flag[N]; //如果flag[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
void Dijkstra(int u)
{
for(int i=1; i<=n; i++)//①
{
dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度
flag[i]=false;
if(dist[i]==INF)
p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
else
p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
}
dist[u] = 0;
flag[u]=true; //初始时，集合S中只有一个元素：源点u
for(int i=1; i<=n; i++)//②
{
int temp = INF,t = u;
for(int j=1; j<=n; j++) //③在集合V-S中寻找距离源点u最近的顶点t
if(!flag[j]&&dist[j]<temp)
{
t=j;
temp=dist[j];
}
if(t==u) return ; //找不到t，跳出循环
flag[t]= true; //否则，将t加入集合
for(int j=1;j<=n;j++)//④//更新集合V-S中与t邻接的顶点到源点u的距离
if(!flag[j]&& map[t][j]<INF)//!flag[j]表示j在V-S中
if(dist[j]>(dist[t]+map[t][j]))
{
dist[j]=dist[t]+map[t][j] ;
p[j]=t ;
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");
cout << "请输入城市的个数："<<endl;
cin >> n;
cout << "请输入城市之间的路线的个数："<<endl;
cin >>m;
cout << "请输入城市之间的路线以及距离："<<endl;
for(int i=1;i<=n;i++)//初始化图的邻接矩阵
for(int j=1;j<=n;j++)
{
map[i][j]=INF;//初始化邻接矩阵为无穷大
}
while(m--)
{
cin >> u >> v >> w;
map[u][v] =min(map[u][v],w); //邻接矩阵储存，保留最小的距离
}
cout <<"请输入小明所在的位置："<<endl; ;
cin >> st;
Dijkstra(st);
cout <<"小明所在的位置："<<st<<endl;
for(int i=1;i<=n;i++){
cout <<"小明："<<st<<" - "<<"要去的位置："<<i<<endl;
if(dist[i] == INF)
cout << "sorry,无路可达"<<endl;
else
cout << "最短距离为:"<<dist[i]<<endl;
}
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
请输入城市的个数：
5
请输入城市之间的路线的个数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入小明所在的位置：
5（3）输出
小明所在的位置：5
小明:5 - 要去的位置:1 最短距离为：8
小明:5 - 要去的位置:2 最短距离为：24
小明:5 - 要去的位置:3 最短距离为：23
小明:5 - 要去的位置:4 最短距离为：30
小明:5 - 要去的位置:5 最短距离为：0想一想：因为我们在程序中使用p[]数组记录了最短路径上每一个结点的前驱，因此除了显示最短距离外，还可以显示最短路径上经过了哪些城市，可以增加一段程序逆向找到该最短路径上的城市序列。
void findpath(int u)
{
int x;
stack<int>s;//利用C++自带的函数创建一个栈s，需要程序头部引入#include<stack>
cout<<"源点为："<<u<<endl;
for(int i=1;i<=n;i++)
{
x=p[i];
while(x!=-1)
{
s.push(x);//将前驱依次压入栈中
x=p[x];
}
cout<<"源点到其他各顶点最短路径为：";
while(!s.empty())
{
cout<<s.top()<<"--";//依次取栈顶元素
s.pop();//出栈
}
cout<<i<<";最短距离为："<<dist[i]<<endl;
}
}只需要在主函数末尾调用该函数：
findpath(st);//主函数中st为源点输出结果如下。
源点为：5
源点到其他各顶点最短路径为：5--1；最短距离为：8
源点到其他各顶点最短路径为：5--1--2；最短距离为：24
源点到其他各顶点最短路径为：5--1--3；最短距离为：23
源点到其他各顶点最短路径为：5--1--3--4；最短距离为：30
源点到其他各顶点最短路径为：5；最短距离为：02.5.6 算法解析及优化拓展
1．算法时间复杂度
（1）时间复杂度：在Dijkstra算法描述中，一共有4个for语句，第①个for语句的执行次数为n，第②个for语句里面嵌套了两个for语句③、④，它们的执行次数均为n，对算法的运行时间贡献最大，当外层循环标号为1时，③、④语句在内层循环的控制下均执行n次，外层循环②从1～n。因此，该语句的执行次数为n*n= n²，算法的时间复杂度为O(n²)。
（2）空间复杂度：由以上算法可以得出，实现该算法所需要的辅助空间包含为数组flag、变量i、j、t和temp所分配的空间，因此，空间复杂度为O(n)。
2．算法优化拓展
在for语句③中，即在集合V−S中寻找距离源点u最近的顶点t，其时间复杂度为O(n)，如果我们使用优先队列，则可以把时间复杂度降为O(log n)。那么如何使用优先队列呢？
（1）优先队列（见附录C）
（2）数据结构
在上面的例子中，我们使用了一维数组dist[t]来记录源点u到顶点t的最短路径长度。在此为了操作方便，我们使用结构体的形式来实现，定义一个结构体Node，里面包含两个成员：u为顶点，step为源点到顶点u的最短路径。
struct Node{
int u,step; // u为顶点，step为源点到顶点u的最短路径
Node(){};
Node(int a,int sp){
u = a; //参数传递，u为顶点
step = sp; //参数传递，step为源点到顶点u的最短路径
}
bool operator < (const Node& a)const{
return step > a.step; //重载 <，step(源点到顶点u的最短路径)最小值优先
}
};上面的结构体中除了两个成员变量外，还有一个构造函数和运算符优先级重载，下面详细介绍其含义用途。
为什么要使用构造函数？
如果不使用构造函数也是可以的，只定义一般的结构体，里面包含两个参数：
struct Node{
int u,step; // u为顶点，step为源点到顶点u的最短路径
};那么在变量参数赋值时，需要这样赋值：
Node vs ; //先定义一个Node结点类型变量
vs.u =3 ,vs.step = 5; //分别对该变量的两个成员进行赋值采用构造函数的形式定义结构体：
struct Node{
int u,step;
Node(){};
Node(int a,int sp){
u = a; //参数传递u为顶点
step = sp; //参数传递step为源点到顶点u的最短路径
}
};则变量参数赋值就可以直接通过参数传递：
Node vs(3,5)上面语句等价于：
vs.v =3 ,vs.step = 5;很明显通过构造函数的形式定义结构体，参数赋值更方便快捷，后面程序中会将结点压入优先队列：
priority_queue <Node> Q; // 创建优先队列，最小值优先
Q.push(Node(i,dist[i])); //将结点Node压入优先队列Q
//参数i传递给顶点u， dist[i]传递给step（3）使用优先队列优化的Dijkstra算法源代码：
//program 2-5
#include <queue>
#include <iostream>
#include<cstring>
#include<windows.h>
using namespace std;
const int N = 100; // 城市的个数可修改
const int INF = 1e7; // 无穷大
int map[N][N],dist[N],n,m;
int flag[N];
struct Node{
int u,step;
Node(){};
Node(int a,int sp){
u=a;step=sp;
}
bool operator < (const Node& a)const{ // 重载 <
return step>a.step;
}
};
void Dijkstra(int st){
priority_queue <Node> Q; // 优先队列优化
Q.push(Node(st,0));
memset(flag,0,sizeof(flag));//初始化flag数组为0
for(int i=1;i<=n;++i)
dist[i]=INF; // 初始化所有距离为，无穷大
dist[st]=0;
while(!Q.empty())
{
Node it=Q.top();//优先队列队头元素为最小值
Q.pop();
int t=it.u;
if(flag[t])//说明已经找到了最短距离，该结点是队列里面的重复元素
continue;
flag[t]=1;
for(int i=1;i<=n;i++)
{
if(!flag[i]&&map[t][i]<INF){ // 判断与当前点有关系的点，并且自己不能到自己
if(dist[i]>dist[t]+map[t][i])
{ // 求距离当前点的每个点的最短距离,进行松弛操作
dist[i]=dist[t]+map[t][i];
Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列，注意：里面的元素有重复
}
}
}
}
}
int main()
{
int u,v,w,st;
system("color 0d");//设置背景及字体颜色
cout << "请输入城市的个数："<<endl;
cin >> n;
cout << "请输入城市之间的路线的个数："<<endl;
cin >>m;
for(int i=1;i<=n;i++)//初始化图的邻接矩阵
for(int j=1;j<=n;j++)
{
map[i][j]=INF;//初始化邻接矩阵为无穷大
}
cout << "请输入城市之间u,v的路线以及距离w："<<endl;
while(m--)
{
cin>>u>>v>>w;
map[u][v]=min(map[u][v],w); //邻接矩阵储存，保留最小的距离
}
cout<<"请输入小明所在的位置："<<endl; ;
cin>>st;
Dijkstra(st);
cout <<"小明所在的位置："<<st<<endl;
for(int i=1;i<=n;i++)
{
cout <<"小明:"<<st<<"--->"<<"要去的位置："<<i;
if(dist[i]==INF)
cout << "sorry,无路可达"<<endl;
else
cout << " 最短距离为："<<dist[i]<<endl;
}
return 0;
}算法实现和测试
（1）运行环境
Code::Blocks
（2）输入
请输入城市的个数：
5
请输入城市之间的路线的个数：
7
请输入城市之间的路线以及距离：
1 2 2
1 3 3
2 3 5
2 4 6
3 4 7
3 5 1
4 5 4
请输入小明所在的位置：
1（3）输出
小明所在的位置：1
小明：1 - 要去的位置：1 最短距离为：0
小明：1 - 要去的位置：2 最短距离为：2
小明：1 - 要去的位置：3 最短距离为：3
小明：1 - 要去的位置：4 最短距离为：8
小明：1 - 要去的位置：5 最短距离为：4在使用优先队列的 Dijkstra 算法描述中，while (!Q.empty())语句执行的次数为n，因为要弹出n个最小值队列才会空；Q.pop()语句的时间复杂度为logn，while语句中的for语句执行n次，for语句中的Q.push (Node(i,dist[i]))时间复杂度为logn。因此，总的语句的执行次数为n* logn+n²*logn，算法的时间复杂度为O(n²logn)。
貌似时间复杂度又变大了？
这是因为我们采用的邻接矩阵存储的，如果采用邻接表存储（见附录D），那么for语句④松弛操作就不用每次执行n次，而是执行t结点的邻接边数x，每个结点的邻接边加起来为边数E，那么总的时间复杂度为O(n*logn+E*logn)，如果E>=n，则时间复杂度为O(E*logn)。
注意：优先队列中尽管有重复的结点，但重复结点最坏是n2，log n2=2 log n，并不改变时间复杂度的数量级。
想一想，还能不能把时间复杂度再降低呢？如果我们使用斐波那契堆，那么松弛操作的时间复杂度O(1)，总的时间复杂度为O(n* logn+E)。
契堆，那么松弛操作的时间复杂度O(1)，总的时间复杂度为O(n* logn+E)。
腾讯云开发者
