一、什么是最短路径
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，这条路径就是两点之间的 最短路径（Shortest Path），其中第一个顶点为 源点（Source），最后一个顶点为 终点（Destination）。
- 单源最短路径问题：从某固定源点触发，求其到所有其它顶点的最短路径；
- 多源最短路径问题：求任意两顶点间的最短路径；
二、无权图的单源最短路径
对于无权图的单源最短路径，我们可以使用广度优先搜索的方法遍历。该方法按层处理顶点，距开始顶点最近的那些顶点首先被赋值，而最短的那些顶点最后被赋值。
首先，我们把从 vertex 开始到顶点的距离放到 distance[] 数组中。开始的时候，除 vertex 外所有的顶点都是不可到达的，而 vertex 的路径长为 0。path[] 用来表示最短路径从哪个顶点过来。visited[] 用来表示节点是否被访问过。起初，所有的顶点都是还没访问的，当一个顶点被表示已知时，我们就有了不会再找到更短的路径的保证，因此对该顶点的处理实质上已经完成了。
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i = 0,j = 0,k = 0;
char data[] = {'A','B','C','D','E','F','G'};
int weight[][sizeof(data)] = {
{0,1,0,1,0,0,0},
{0,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,0,1,0,1,1,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
Graph graph = StructureGraph(sizeof(data),data,weight);
Unweighted(graph,0);
return 0;
}
/**
* @brief 构建一个图
*
* @param N 顶点个数
* @param data 顶点数据数组
* @param weight 边的权值数组
* @return Graph 返回构建的图
*/
Graph StructureGraph(int N,int data[N],int weight[N][N])
{
int i = 0, j = 0;
Graph graph = CreateGraph(N);
for(i = 0; i < graph->vertexNum; i++)
{
graph->vertex[i] = data[i];
}
for(i = 0; i < graph->vertexNum; i++)
{
for(j = 0; j < graph->vertexNum; j++)
{
if(weight[i][j] != 0)
{
Edge edge = malloc(sizeof(struct ENode));
edge->v1 = i;
edge->v2 = j;
edge->weight = weight[i][j];
InsertEdge(graph,edge);
}
}
}
return graph;
}
/**
* @brief 无权图的单源最短路
*
* @param graph 待操作的图
* @param vertex 待访问的第一个节点
*/
void Unweighted(Graph graph,int vertex)
{
int distance[graph->vertexNum]; // 表示从vertex到第i个节点的最短路径
int path[graph->vertexNum]; // 最短路径从哪个顶点过来
int i = 0,j = 0;
int v = 0,w = 0;
Queue Q = CreateQueue();
for(i = 0; i < graph->vertexNum; i++)
{
distance[i] = -1;
path[i] = -1;
}
distance[vertex] = 0;
Enqueue(Q,vertex);
while(!QueueIsEmpty(Q))
{
v = Dequeue(Q);
for(w = GetFirstNeighbor(graph,v); w >= 0; w = GetNextNeighbor(graph,v,w))
{
if(distance[w] == -1) // w为s尚未访问的邻接顶点
{
distance[w] = distance[v]+1; // 最短长度加1
path[w] = v; // 最短路径应从v到w
Enqueue(Q,w); // 顶点w入队
}
}
}
// 程序执行到此，从vertex到图中其它节点的最短路径保存再path数组，最短路径长度保存在distance数组中
PrintPath(graph,vertex,distance,path);
}
/**
* @brief 得到第一个邻接节点的下标
*
* @param graph 待操作的图
* @param index 对应节点的下标
* @return int 如果存在返回对应的下标，否则返回-1
*/
int GetFirstNeighbor(Graph graph,int index)
{
int j = 0;
for(j = 0; j < graph->vertexNum; j++)
{
if(graph->edge[index][j] > 0)
{
return j;
}
}
return -1;
}
/**
* @brief 根据前一个邻接节点的下标获取下一个邻接节点
*
* @param graph 待操作的图
* @param v1 对应节点的下标
* @param v2 上一个邻接节点的下标
* @return int
*/
int GetNextNeighbor(Graph graph,int v1,int v2)
{
int j = 0;
for(j = v2+1; j < graph->vertexNum; j++)
{
if(graph->edge[v1][j] > 0)
{
return j;
}
}
return -1;
}
/**
* @brief 输出vertex节点到图中其它节点的最短路径
*
* @param graph 待操作的图
* @param vertex 开始的节点的下标
* @param distance vertex到图中其它节点距离的数组
* @param path vertex到图中其它节点路径的数组
*/
void PrintPath(Graph graph,int vertex,int distance[],int path[])
{
int i = 0,j = 0;
for(i = 0; i < graph->vertexNum; i++)
{
j = i;
if(i != vertex)
{
Stack S = CreateStack();
printf("%c → %c : ",graph->vertex[vertex],graph->vertex[i]);
printf("distance = %d,",distance[i]);
printf("path = { ");
while(path[j] != -1)
{
Push(S,path[j]);
j = path[j];
}
while(!StackIsEmpty(S))
{
j = Pop(S);
printf("%c → ",graph->vertex[j]);
}
printf("%c }\n",graph->vertex[i]); // 终点
}
}
}
时间复杂度 \(T = O(|V| + |E|)\)
三、有权图的单源最短路径
有权图的单元最短路径可以用 Dijkstra（迪杰斯特拉）算法解决，他啊用于计算一个节点到其它节点的最短路径。它的主要特点是以起始点为中心向外层扩展（广度优先搜索思想），直到扩展到终点为止。
设置出发节点为 vertex，顶点集合 \(V\{v_{1},v_{2},...\}\)，vertex 到 V 中各顶点的距离构成距离集合 distance，\(distance\{d_{1},d_{2},...\}\)，distance 集合记录着 vertex 到图中各顶点的距离（到自身的距离可以看做 0，vertex 到 \(v_{i}\) 的距离对应 \(d_{i}\)。
Dijkstra 算法按阶段进行，正像无权最短路径算法。在每个阶段，Dijkstra 算法选择一个顶点 v，它在所有位置未知顶点中具有最小的 \(d_{v}\)，同时算法声明从 s 到 v 的最短路径是已知的。阶段的其余部分有 \(d_{w}\) 的值的更新工作组成。
- 从 distance 中选择值最小的 \(d_{i}\) 并移出 distance 集合，同时移出 V 集合中对应的顶点 \(v_{i}\)，此时的 vertex 到 \(v_{i}\) 即为最短路径；
- 更新 distance 集合，更新规则为：比较 vertex 到 V 集合中顶点的距离值，与 vertex 通过 \(v_{i}\) 到 V 集合中顶点的距离值，保留值较小的一个（同时也应该更新顶点的前驱节点为 \(v_{i}\)，表示是通过 \(v_{i}\) 到达的）；
- 重复执行两步骤，直到最短路径顶点为目标顶点即可结束；
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i = 0,j = 0,k = 0;
char data[] = {'A','B','C','D','E','F','G'};
int weight[][sizeof(data)] = {
{0,2,0,1,0,0,0},
{0,0,0,3,10,0,0},
{4,0,0,0,0,5,0},
{0,0,2,0,2,8,4},
{0,0,0,0,0,0,6},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
Graph graph = StructureGraph(sizeof(data),data,weight);
Dijkstra(graph,0);
return 0;
}
/**
* @brief Dijkstra算法
*
* @param graph
* @param vertex
*/
void Dijkstra(Graph graph,int vertex)
{
int distance[graph->vertexNum]; // 表示从vertex到第i个节点的最短路径
int path[graph->vertexNum]; // 最短路径从哪个顶点过来
int collected[graph->vertexNum]; // 表示节点是否被收集过
int i = 0,j = 0;
int min = 9999;
int v = 0,w = 0,s = 0;
for(i = 0; i < graph->vertexNum; i++)
{
distance[i] = 65535;
path[i] = -1;
collected[i] = 0;
}
distance[vertex] = 0;
collected[vertex] = 1;
for(i = 0; i < graph->vertexNum; i++)
{
min = 9999;
for (s = 0; s < graph->vertexNum; s++) //选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
{
if (!collected[s]) // 如果该顶点还未被收集
{
if (distance[s] < min)
{
v = s;
min = distance[s];
}
}
}
collected[v] = 1; // 标记v为已经被收集
for(w = GetFirstNeighbor(graph,v); w >= 0; w = GetNextNeighbor(graph,v,w))
{
if(!collected[w]) // w为v尚未访问的邻接顶点
{
if(distance[v] + graph->edge[v][w] < distance[w])
{
distance[w] = distance[v] + graph->edge[v][w]; // 最短长度加1
path[w] = v; // 最短路径应从v到w
}
}
}
}
// 程序执行到此，从vertex到图中其它节点的最短路径保存再path数组，最短路径长度保存在distance数组中
PrintPath(graph,vertex,distance,path);
}
如果直接扫描搜友未收录顶点，它的时间复杂度为 \(T = O(|V|^{2} + |E|)\)
如果将 dist 在最小堆中，它的时间复杂度为 \(T = O(|E| + log|v|)\)
四、多源最短路径
我们可以直接将单源最短路径算法调用 |V| 遍，此时它的时间复杂度为 \(T = O(|V|^{3} + |E|*|V|)\)，对于稀疏图的效果比较好。对于稠密图来说，推荐使用 Floyd 算法，它的时间复杂度为 \(T = O(|V|^3)\)。
Floyd 算法中每一个顶点都是出发访问节点，所以需要将每一个节点看做被访问顶点，求出从每一个顶点到其它顶点的最短路径。Floyd 算法的步骤如下：
- 设置顶点 \(v_{i}\) 到顶点 \(v_{k}\) 的最短路径已知为 lik，顶点 \(v_{k}\) 到 \(v_{j}\) 的最短路径已知 lkj，顶点 \(v_{i}\) 到 \(v_{j}\) 的路径为 lij，则 \(v_{i}\) 到 \(v_{j}\) 的最短路径为：min((lik,+lij),lij)，\(v_{k}\) 的取值为图中所有顶点，则可获得 \(v_{i}\) 到 \(v_{j}\) 的最短路径；
- 至于 \(v_{i}\) 和 \(v_{k}\) 的最短路径 lik 或者 \(v_{k}\) 到 \(v_{j}\) 的最短路径为 lkj，是以同样的方式获得；
初始化时设置一个 n 阶方阵，另其对角元素为 0，若存在边 \(<v_{i},v_{j}>\) ，则对应元素为权值，否则为 ∞。逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之。否则，维持原值。所有顶点试探完毕，算法结束。
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int i = 0,j = 0,k = 0;
char data[] = {'A','B','C','D','E','F','G'};
int weight[][sizeof(data)] = {
{0,5,7,0,0,0,2},
{5,0,0,9,0,0,3},
{7,0,0,0,8,0,0},
{0,9,0,0,0,4,0},
{0,0,8,0,0,5,4},
{0,0,0,4,5,0,6},
{2,3,0,0,4,6,0}
};
Graph graph = StructureGraph(sizeof(data),data,weight);
Floyd(graph);
return 0;
}
/**
* @brief Floyd算法
*
* @param graph 待操作的图
*/
void Floyd(Graph graph)
{
int i = 0,j = 0,k = 0;
int distance[graph->vertexNum][graph->vertexNum];
int path[graph->vertexNum][graph->vertexNum];
for(i = 0; i < graph->vertexNum; i++)
{
for(j = 0; j < graph->vertexNum; j++)
{
distance[i][j] = graph->edge[i][j];
if((graph->edge[i][j] == 0) && (i != j))
{
distance[i][j] = 65535;
}
path[i][j] = -1;
}
}
for(k = 0; k < graph->vertexNum; k++) // 中间顶点
{
for(i = 0; i < graph->vertexNum; i++) // 出发顶点
{
for(j = 0; j < graph->vertexNum; j++) // 终点顶点
{
// distance[i][k] + distance[k][j] 为从 i 顶点出发，经过 k 顶点，到达 j 顶点的距离
// distance[i][j] 为 i 顶点和 j 顶点直连的距离
if(distance[i][k] + distance[k][j] < distance[i][j])
{
distance[i][j] = distance[i][k] + distance[k][j]; // 更新距离
path[i][j] = k; // 更新前驱顶点
}
}
}
}
for(i = 0; i < graph->vertexNum; i++)
{
PrintPath(graph,i,distance[i],path[i]);
}
}