Dijkstra算法概述：
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个顶点到其他所有顶点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。（引用）
大概思路是：将所有顶点分为 已找到到起始点的最短路径的顶点 和 未找到到起始点的最短路径的顶点 两部分,用一个bool数组Final记录。dist[i]记录顶点i到起始点的最短距离,在Final==0的顶点中，找出最小dist，将对应的顶点 标记为已找到最小路径即其Final==1，由于新增一条最短路径，其他顶点到起始点的最短距离会发生改变，将Final==0的顶点依次通过其相邻顶点中Final==1的顶点到达起始点的距离相比较，选出最小值及最小值对应的Final==1的顶点，该值为该Final==0顶点到起始点的最短距离，则该顶点到起始点的最短路径已找到，置该点的Final==1。该Final==1顶点为该Final==0顶点的前一顶点，用prior[i]记录顶点i的前一顶点。以此类推，直到所有点的Final都等于0， 即所有顶点到起始点的最短路径均找到。 由于顶点的最短路径依赖于另一个顶点的最短路径，这种算法必须依次求出各个顶点的最短路径直到目标终止顶点。
算法步骤及解释：
- 最开始所有顶点到起始点的最短路径都没找到，初始化所有顶点的Final为0。将起始点标记，Final[0]=1,记录顶点i到起始顶点的最短距离dist[i],若顶点i与起始顶点不相邻，则dist[i]为infinity
- 找到dist[i]中的最小值，将对应的顶点v标记，v的Final置为1，v的前一顶点prior[v]为起始顶点，即找到v到起始顶点的最短路径
- 由于新添加了一条最短路径，其他Final为0的顶点v到起始点的最短路径可以通过与v相邻且已知最短路径的顶点，也就是说v到起始点的最短距离可能改变，得更新。v到初始顶点最短路径有3种情况：1.一条边直通起始点 2.通过其已知最短路径的相邻顶点到起始点（通过局部最近得到整体最近） 3.原路径对应的最小距离，将这3种情况得到的所有最短距离比较，选出最小值为dist[v]及得到该最小值通过的那个相邻顶点为v的前一顶点prior[v]
- 重复步骤2，3直到所有顶点的Final值均为1，即所有顶点到起始顶点的的最短路径都找到了
图例
eg：对于原图
1.将起始点v0加入最短路径中并将其标记，Final[0]=1，起始点在其最短路径中没有上一顶点，prior[0]记为-1。记录其他点到v0的最短距离dist，若与起始点不相邻则dist为infinity
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| prior | -1 | ||||||||
| dist | 0 | 4 | 8 |
2.选出dist中未找到最短路径的顶点（Final==0）到起始顶点的的最短距离（dist）中的最小值4对应的顶点v1，则找到v1的最短路径(置Final[1]=1)，v1的前一顶点是v0（置prior[1]=0）,v1到顶点最短距离为4（置dist[1]=4）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| prior | -1 | 0 | |||||||
| dist | 0 | 4 | 8 |
3.由于新添加了一条最短路径，v2可以通过与v2相邻且已知最短路径的顶点v1到达v0，v2到初始顶点v0的最短路径有3种情况：1.一条边直通起始点（距离为infinity） 2.通过其已知最短路径的相邻顶点v1到起始点（距离为8+4=12）3.原路径对应的最小距离，选出最小值12为dist[2]，则prior[2]=1,更新表
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| prior | -1 | 0 | 1 | ||||||
| dist | 0 | 4 | 12 | 8 |
4.选出Final==0的顶点中dist最小值8对应的顶点v7，则找到v7的最短路径(置Final[7]==1)，v7的前一顶点是v0（置prior[7]=0）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| prior | -1 | 0 | 0 | ||||||
| dist | 0 | 4 | 12 | 8 |
5.由于新添加了一条最短路径，v6,v8可以通过与其相邻且已知最短路径的顶点v7到达v0，v6，v8到初始顶点v0的最短路径有3种情况：1.一条边直通起始点 2.通过其已知最短路径的相邻顶点v7到起始点 3.原路径对应的最小距离，分别选出v6,v8的最短距离9，15，则prior[6]=7,prior[8]=1,更新表
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| prior | -1 | 0 | 0 | ||||||
| dist | 0 | 4 | 12 | 9 | 8 | 15 |
6.选出Final==0的顶点中dist最小值9对应的顶点v6，则找到v6的最短路径(置Final[6]==1)，v6的前一顶点是v7（置prior[6]=7）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| prior | -1 | 0 | 7 | 0 | |||||
| dist | 0 | 4 | 12 | 9 | 8 | 15 |
7.由于新添加了一条最短路径(v6)，v5,v8可以通过与其相邻且已知最短路径的顶点v6到达v0，v5，v8到初始顶点v0的最短路径有3种情况：1.一条边直通起始点 2.通过其已知最短路径的相邻顶点v7到起始点 3.原路径对应的最小距离，分别选出v5,v8的最短距离11，15，则prior[5]=6,prior[8]=6更新表
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| prior | -1 | 0 | 7 | 0 | |||||
| dist | 0 | 4 | 12 | 11 | 9 | 8 | 15 |
8.选出Final==0的顶点中dist最小值11对应的顶点v5，则找到v5的最短路径(置Final[5]==1)，v5的前一顶点是v6（置prior[5]=6）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| prior | -1 | 0 | 6 | 7 | 0 | ||||
| dist | 0 | 4 | 12 | 11 | 9 | 8 | 15 |
9.由于新添加了一条最短路径(v5)，Final为0的v3,v4可以通过与其相邻且已知最短路径的顶点v5到达v0，v3,v4到初始顶点v0的最短路径有两3情况：1.一条边直通起始点 2.通过其已知最短路径的相邻顶点v5到起始点 3.原路径对应的最小距离， 分别选出v3,v4的最短距离25，21，则prio[3]=5,prior[4]=5,更新表
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| prior | -1 | 0 | 6 | 7 | 0 | ||||
| dist | 0 | 4 | 12 | 25 | 21 | 11 | 9 | 8 | 15 |
10.选出Final==0的顶点中dist最小值12对应的顶点v2，则找到v2的最短路径(置Final[2]==1)，v2的前一顶点是v1（置prior[2]=1）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| prior | -1 | 0 | 1 | 6 | 7 | 0 | |||
| dist | 0 | 4 | 12 | 25 | 21 | 11 | 9 | 8 | 15 |
11.由于新添加了一条最短路径(v2)，Final为0的v3,v8可以通过与其相邻且已知最短路径的顶点v2到达v0，v3,v8到初始顶点v0的最短路径有3种情况：1.一条边直通起始点 2.通过其已知最短路径的相邻顶点v2到起始点 3.原路径对应的最小距离，分别选出v3,v8的最短距离19，14，则prior[3]=2,prior[8]=2,更新表
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| prior | -1 | 0 | 1 | 6 | 7 | 0 | |||
| dist | 0 | 4 | 12 | 19 | 21 | 11 | 9 | 8 | 14 |
依次类推。。。
最后得到的结果为：
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Final | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| prior | -1 | 0 | 1 | 2 | 5 | 6 | 7 | 0 | 2 |
| dist | 0 | 4 | 12 | 19 | 21 | 11 | 9 | 8 | 14 |
代码：
#include <iostream>
#include <iomanip>
#include "graph.h"
using namespace std;
/**
按最短路径（SP）长度递增生成,求源点到其余各顶点的SP，及长度
* 相关数据结构,若已求得v到i的SP：
则Final[i]=true;SP可从 prior[i]回溯到源点即得;SP长度记录于dist[i]
@g 邻接矩阵表示的有向网
@v 源点编号
@dist 记录源点到各顶点的（当前所得）SP的长度
@prior 记录n-1条最短路径. prior[k]:最短路径上,第k顶点的前驱顶点号*/
void Dijkstra(MGraph g, int v, float dist[], int prior[])
{
int n = g.vexnum;
bool Final[n];
int i, j, k;
float w, min;
/**设置初始状态 */
for (i = 0; i < n; i++)
{
Final[i] = false;
// 初始,各点的SP只能为由源点直达i,相应设置dist，prior
dist[i] = g.arcs[v][i];
if (i!=v && dist[i] <INFINITY)
prior[i] = v; // 源点直达,故终点前驱为源点
else
prior[i] = -1; //源点至i无路,或i即为源点
}
Final[v] = true; // 源点v也即终点
/** 按长度递增，求源点v到各顶点的SP*/
for (i = 0; i < n-1; i++)
{
/** 选择:挑选最短的SP（其经过的顶点全来自S） */
int u;
min = INFINITY;
for (j = 0; j < n; j++)
{
if (!Final[j] && dist[j] < min)
{
u = j;
min = dist[j];
}
}
Final[u] = true; //v到u的SP已求得,则顶点u加入集S
/**更新状态:以新选择的顶点u,来更新dist和prior向量 */
for (k = 0; k < n; k++)
{
w = g.arcs[u][k];
/* 若从顶点u "扩展"一条边<u,k>的SP长度更短 */
if (!Final[k] && w < INFINITY &&
dist[u]+w < dist[k] )
{
dist[k] = dist[u] + w; //更新SP长度
prior[k] = u; // 更新SP，顶点k的前驱是u
}
} //for
}
}
/** 递归：输出从源点s(prior[s]=-1)到v的SP,从v回溯到s.
Note: Dijkstra算法和Floyd算法,均以此函数来输出某源点到各点的SP */
void Traceback(MGraph g, int prior[],int v)
{
if( prior[v] == -1 )
{
cout << g.vexs[v] << " ";
return;
}
Traceback(g,prior,prior[v]);
cout << g.vexs[v] << " ";
}
/** 输出从源点s到v的各条SP,及其长度 */
void Dijkstra_SP(MGraph g, int v)
{
int n = g.vexnum;
float dist[n];
int prior[n];
Dijkstra(g,v,dist,prior);
cout << "Shortest Path from " << g.vexs[v] << endl;
for(int i=0; i<n; i++)
{
if(i==v || dist[i] == INFINITY) //i为源点,或源点到i无路径,就算哒
continue;
cout <<"\t sp_len = " << dist[i] << " "; //输出SP长度
Traceback(g,prior,i); //输出SP
cout << endl;
}
}
输出结果：
-------- Dijkstra ----------
Shortest Path from A
sp_len = 10 A C
sp_len = 50 A E D
sp_len = 30 A E
sp_len = 60 A E D F
--------------------------------
