数据结构面试之八——图的常见操作2之最短路径
数据结构面试之九——图的常见操作2之最短路径
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
八、图的常见操作2之最短路径
（一）最短路径核心思想步骤如下：
（1）从选定的源顶点出发，先选择与该源顶点相连的权值最小且尚未标识过的顶点X，并标识X为True、记录该路径长度；
（2）然后比较经过该顶点X与其余顶点相连的路径之和是否小于源顶点到其余顶点的直接路径长度，是，则修改路径长度；否，则保持不变；
（3）循环执行（1），直至所有的顶点都标识为True。
为了便于理解，执行步骤图示如下几个表格。初始图结构表示如下：表格内值为顶点之间的权重，如（Vertex4,Vertex1）=10 代表顶点4与顶点1之间的路径权重为10。
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
Vertex 0
0
16
∞
2
3
Vertex 1
∞
0
5
∞
∞
Vertex 2
∞
3
0
∞
∞
Vertex 3
∞
12
∞
0
7
Vertex 4
∞
10
4
5
0
假定求解从顶点0到其余各顶点的最短路径长度。
前提：初始化操作，将0到各顶点的权重值存储到数组weights[][]中；将最小权重发现标识存储到数组weightFound[]中，并初始化weightFound[0]=true(因为0为源点)。
第1步：查找并选定顶点0到其余各顶点的最小权重值的顶点，且要求查找的点尚未被标识过true。显然，此处选择顶点Vertex3。
算法的执行步骤如下图所示：
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
原始权值
0
16
∞
2
3
选定v3后
修改权重
0
（0->3->1）
14
（0->3->2）
∞
2
（0->3->4）
9
比较取小值
0
14
∞
2
3
标识
True
False
False
True
False
第2步：查找并选定顶点0到其余各顶点的最小权重值的顶点，且该点尚未被标识过true。
显然，此处选择顶点Vertex 4。
算法的执行步骤如下图所示：
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
原始权值
0
14
∞
2
3
选定v4后
修改权重
0
（0->4->1）
13
（0->4->2）
7
（0->4->3）
8
3
比较取小值
0
13
7
2
3
标识
True
False
False
True
True
第3步：查找并选定顶点0到其余各顶点的最小权重值的顶点，且该点尚未被标识过true。
显然，此处选择顶点Vertex 2。
算法的执行步骤如下图所示：
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
原始权值
0
13
7
2
3
选定v2后
修改权重
0
（0->2->1）
10
7
（0->2->3）
∞
（0->2->4）
∞
比较取小值
0
10
7
2
3
标识
True
False
True
True
True
第4步：查找并选定顶点0到其余各顶点的最小权重值的顶点，且该点尚未被标识过true。
显然，此处选择顶点Vertex 1。
算法的执行步骤如下图所示：
Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4
原始权值
0
10
7
2
3
选定v1后
修改权重
0
10
（0->1->2）
15
（0->1->3）
∞
（0->1->4）
∞
比较取小值
0
10
7
2
3
标识
True
True
True
True
True
至此，所有标记都为True，比较结束。顶点0到其余各点的最短路径分别如下：
Vertex 0到其余各顶点
Vertex 1
Vertex 2
Vertex 3
Vertex 4
最短路径
10
7
2
3
template <class vType, int size>voidweightedGraphType<vType,size>::printShortestDistance(vType vertex){ cout<< "Source vertex: " << vertex << endl; cout<< "Shorest distance from source to each vertex" << endl; cout<< "Vertex Shortest_Distance" << endl; shortestPath(vertex); for(int j = 0; j < gSize; j++) { cout<< setw(4) << j << setw(12) << smallestWeight[j]<< endl; } cout<< endl;}