图的最短路径
最小生成树与最短路径
最小生成树
- 包含图中的所有点。
- 能保证整个树中的所有路径之和最小。
最短路径
- 不一定包含图中的所有结点。（有向图，部分结点无法以最短路方式被加入）
- 能保证从一点到图中其他点的路径最小。
Dijkstra迪杰斯特拉算法
Dijkstra按路径长度递增的次序产生最短路径，最终得到的是从图中某个顶点到所有其他（存在最短路）的顶点的最短路径。
算法步骤
- 把图中所有顶点分为两组：已求出最短路的和未求出最短路的，前者初始时只包含源点v0；
- 按与源点的最短路长度依次递增的顺序，逐个把未求出最短路的集合中的顶点加入已求出最短路的结点，同时每加入一个新结点，都要对其他结点的最短路长度进行更新。
- 最终所有结点都被加入已求出最短路的结点。
辅助数据结构
- 一维数组
S[i]
用于标记结点是否已经被求出了最短路径。 - 一维数组
Path[i]
记录每个结点的直接前驱结点的编号。 - 一维数组
D[i]
记录从源点到每个结点的当前最短路长度。
如果加入新结点后，发现某些结点以新加入的结点作为中转结点会使其到源点的最短路径比当前已求出的最短路径更小，则需要对其进行更新。更新后再选择D中值最小的结点，重复上述步骤。
算法实现
void ShortestPath_DIJ(AMGraph G, int v0) {
n = G.vexnum;
for(v = 0; v < n; v++) {
S[v] = false; D[v] = G.arcs[v0][v];
Path[v] = (D[v] < MaxInt) ? v0 : -1; // 不与源点直接相连的 最短路长度初始化为-1
}
S[v0] = true; D[v0] = 0; // 加入源点 下面是主循环
for(i = 1; i < n; i++) {
min = MaxInt;
for(w = 0; w < n; w++)
if(!S[w] && D[w] < min) {v = w; min = D[w];}
S[v] = true;
for(w = 0; w < n; w++) {
if(!S[w] && (D[v] + G.arcs[v][w] < D[w]))
// 加入新结点后 对之前求出的其它结点最短路径长度进行更新
D[w] = D[v] + G.arcs[v][w], Path[w] = v;
}
}
}
算法分析
时间复杂度为O(n²)。
即使是只想知道从源点到某个特定结点的最短路，也需要完整执行一次Dijkstra算法。
Floyd弗洛伊德算法
Floyd算法用求每一对结点之间的最短路径，也可以调用n次Dijkstra算法解决，但Floyd更优雅。两者时间复杂度都是O(n³)。
就是遍图中的所有结点，每次都把遍历到的当前结点作为中转结点进行插入（就是考察如果加上这个新结点，现有的所有最短路径长度会不会更新）。
算法步骤
- 在两顶点间插入一个中转结点（也就是给二维数组赋值），通过比较两种方式的路径长度，得到两顶点间的最短路径长；
- 不断重复上述步骤，每插入一个新结点，就更新一次所有的最短路径值。
辅助数据结构
- 二维数组
D[i][j]：记录两顶点间最短路长度。 - 二维数组
Path[i][j]：记录两顶点间的中转结点，便于中间过程进行比较更新。
算法实现
void ShortestPath_Floyd(AMGraph G) {
for(i = 0; i < G.vexnum; i++) // 初始化
for(j = 0; j < G.vexnum; j++) {
D[i][j] = G.arcs[i][j];
Path[i][j] = (D[i][j] < MaxInt && i != j) ? i : -1;
}
for(k = 0; k < G.vexnum; k++)
for(i = 0; i < G.vexnum; i++)
for(j = 0; j < G.vexnum; j++)
if(D[i][k] + D[k][j] < D[i][j]) {
// 通过比较两顶点间的 当前最短路径长度 与 经过中转结点的最短路径长度
// 得到更小的一个作为新的最短路径长度
D[i][j] = D[i][k] + D[k][j];
Path[i][j] = Path[k][j];
}
}