/背景/
在图论的学习中，非常有实用性的一个课题：最短路径。
这里讨论一下Dijkstra算法求最短路径。
**用于图中某一顶点到其余各顶点的最短路径。
/理论/
Dijkstra的主要思想是分两个集合存放结点。S集合存放已确定路径会经过的顶点，T集合存放暂时查到最短路径但还未确定的顶点。从出发点开始，每次遍历S集合最新节点的可达到节点路径，计算最短路径后存入T集合，最短路径到达的节点入S集合，直至所有节点遍历结束。这个算法的主要思想也可以用贪心算法来总结。每次获取下一段最短路径，上一段都已经是最短路径。
/实 现/
Dijkstra的实现主要使用三个辅助数组。
- dist[]表示当前S最新节点至可到达节点的最短距离。不可直达的暂不计算。
- path[]表示当前S最新节点最短路径的上一个节点。
- set[]标记已入S集合的节点。
来看一道例题，了解下算法。
以顶点0为起点：
dist[1] = 4 < dist[2] = 6 < dist[3] = 6
dist[4] = dist[1] + dist[1][4] = 11
以1为中转点检测
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 11 | - | - |
| Path | -1 | 0 | 1 | 0 | 1 | -1 | -1 |
| Set | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
dist[2] = 6 > dist[1] + dist[1][2] = 5
dist[3]=6 < dist[1] + dist[1][2] + dist[2][3] = 7 < dist[2] + dist[2]dist[3] = 8
dist[4] = dist[1]+dist[1][4] = 11 (以下省略遍历步骤，只给出最短路径)
dist[5] = dist[1] + dist[1][2] +dist[2][5] = 9
以2为中转点检测
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 11 | 9 | - |
| Path | -1 | 0 | 1 | 0 | 1 | 2 | -1 |
| Set | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
dist[4] = 11
dist[5] = 9
以3位中转点检测
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 11 | 9 | - |
| Path | -1 | 0 | 1 | 0 | 1 | 2 | -1 |
| Set | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
** dist[4] = dist[1] + dist[1][2] + dist[2][5] + dist[5][4] = 10 （注意：此处更新了4的路径）
** dist[6] = dist[1] + dist[1][2] + dist[2][5] + dist[5][6] = 17 (注意：此处4还未入S集合，所以最短路径只能走5)
以5为中转点检测（因为5比4路径短）
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 10 | 9 | 17 |
| Path | -1 | 0 | 1 | 0 | 1 | 2 | 5 |
| Set | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
dist[5] = 9
dist[6] = dist[1] + dist[1][2] + dist[2][5] + dist[5][4] + dist[4][6] = 16
以4为中转点检测
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 10 | 9 | 16 |
| Path | -1 | 0 | 1 | 0 | 5 | 2 | 4 |
| Set | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
所有节点并入
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| Dist | 0 | 4 | 5 | 6 | 10 | 9 | 16 |
| Path | -1 | 0 | 1 | 0 | 5 | 2 | 4 |
| Set | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
再来看一下实现代码：
// 图的定义 顺序存储
typedef struct
{
int edges[maxSize][maxSize];
// 邻接矩阵定义，如果是有权图，则在此句中将int改为float
int n, e; // 分别为顶点数和边数
VertextType vex[maxSize];
}MGraph;
// Dijkstra path数组。内容是一棵双亲存储结构的树。
void printfPath(int path[], int a)
{
int stack[maxSize], top = -1;
while (path[a] != -1)
{
stack[++top] = a;
a = path[a];
}
stack[++top] = a;
while (top != -1)
{
cout<<stack[top--]<<" ";
}
cout<<endl;
}
//Dijkstra
void Dijkstra(MGraph g, int v, int dist[], int path[])
{
int set[maxSize];
int min, i, j, u;
// 初始化各个数组
for ( i = 0; i < g.n; ++i)
{
dist[i] = g.edges[v][i];
set[i] = 0;
if (g.edges[v][i] < INF)
{
path[i] = v;
}
else
{
path[i] = -1;
}
}
set[v] = 1;
path[v] = -1;
// 初始化结束 开始关键操作
for ( i = 0; i < g.n-1; ++i)
{
min = INF; // INF是一个常量 要比所有权值大 为了获得最小值
for ( j = 0; j < g.n; ++j) // 每次从未入S集合的点中获取路径最短的点
{
if (set[j] == 0 && dist[j] < min)
{
u = j;
min = dist[j];
}
}
set[u] = 1; // 入S集合
for ( j = 0; j < g.n; ++j)
{
if (set[j]==0 && dist[u] + g.edges[u][j] < dist[j]) // 如果有更短的路径 进行更新
{
dist[j] = dist[u] + g.edges[u][j];
path[j] = u;
}
}
}
}
有时候看文字看不懂，可以考虑做题试试，也许迎刃而解 :P
