基本思想
- 假定一个源点u，顶点集合V被划分成两个部分：集合 S 和集合 V-S 。
- 初始时S仅包含源点u，S中的顶点到源点u的最短距离已经确定，V-S中的顶点到源点u的最短距离待定。
- 用数组dist[]记录每个顶点到源点u的最短距离。
算法流程
- 数据结构：设地图的带权邻接矩阵为map[][]，如果源点u到顶点i有边，则map[u][i]为<u,i>的权值，否则map[u][i]为∞。利用一位数组dist[i]记录顶点i到源点u的最短路径。
- 初始化， 令集合S = {u}，对于集合V-S中的所有顶点i，初始化dist[i]=map[u][i]。如果源点u与顶点i有边相连，初始化p[i]=u，否则p[i]=-1，p[]用来记录当前顶点i的前驱节点。
- 找最小，在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t，即dist[t]=min(dist[j] | j属于V-S集合)，那么顶点t就是此时V-S中距离源点u最近的顶点。
- 将t加入S集合， 同时更新V-S集合，也要更新与顶点t相连的其他顶点到源点u的距离。假设V-S集合中的顶点j与刚加入到S集合中的顶点t有边权值为map[t][i]，如果dist[j] > dist[t] + map[t][i]，则dist[j] = dist[t] + map[t][i]，且更新顶点j的前驱p[j]=t，否则dist[j]保持不变。
- 判断集合S-V是否为空，若为空了，结束算法，否则跳转第3步。
最终dist[]数组记录了每个顶点到源点u的最短距离。
p[j]记录了顶点j到源点u的最短路径上的前驱节点，通过p[]能找到顶点j到源点u最短路径的路线。
一个简单的例子
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 100;//城市数量
const int INF = 1e7;//初始化无穷大值
int map[N][N], dist[N], p[N], n, m;//n为城市的个数，m为城市间路线的条数
bool flag[N];//flag[i]为true，表明顶点i已加入到集合S
void Dijkstra(int u)
{
for(int i=1; i<=n; i++)
{
dist[i] = map[u][i];//初始化源点u到各个顶点的距离
flag[i] = false;
if(dist[i] == INF)
p[i] = -1;//源点u到该顶点的距离无穷大，说明i点与源点不相邻
else
p[i] = u;
}
dist[u] = 0;
flag[u] = true;//初始化时，集合S中只有一个元素，即源点u
for(int i=1; i<=n; i++)
{
int temp = INF, t = u;
for(int j=1; j<=n; j++)//在集合V-S中寻找距离源点u最近的顶点t
{
if(!flag[j]&&dist[j]<temp)
{
t = j;
temp = dist[j];
}
}
if(t==u) return;//找不到t，跳出循环
flag[t] = true;//否则将t加入S集合
for(int j=1; j<=n; j++)//更新集合V-S中与t相邻的顶点到源点u的距离
{
if(!flag[j]&&map[t][j]<INF)
if(dist[j]>(dist[t]+map[t][j]))
{
dist[j] = dist[t] + map[t][j];
p[j] = t;
}
}
}
}
int main()
{
int u, v, w, st;
cout << "请输入城市的个数：" << endl;
cin >> n;
cout << "请输入城市之间路线的条数：" << endl;
cin >> m;
cout << "请输入城市之间的路线以及距离：" << endl;
for(int i=1; i<=n; i++)//初始化邻接矩阵
for(int j=1; j<=n; j++)
map[i][j] = INF;//初始化邻接矩阵为无限大
while(m--)
{
cin >> u >> v >> w;
map[u][v] = min(map[u][v], w);//保留最小距离
}
cout << "请输入当前所在位置：" << endl;
cin >> st;
Dijkstra(st);
cout << "起点所在位置：" << st << endl;
for(int i=1; i<=n; i++)
{
cout << "起点：" << st << " - " << "目的地：" << i << " ";
if(dist[i] == INF)
cout << "无法到达" << endl;
else
cout << "最短距离为：" << dist[i] << endl;
}
return 0;
}
输入和输出
请输入城市的个数：
5
请输入城市之间路线的条数：
11
请输入城市之间的路线以及距离：
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
请输入当前所在位置：
5
起点所在位置：5
起点：5 - 目的地：1 最短距离为：8
起点：5 - 目的地：2 最短距离为：24
起点：5 - 目的地：3 最短距离为：23
起点：5 - 目的地：4 最短距离为：30
起点：5 - 目的地：5 最短距离为：0
- 城市之间的距离是用有向图来表示的，路径表示都是单向的，如上面输入的1 5 12，是指城市1到城市5有一条路长度为12，不代表城市5到城市1有路可走。
- 若要表示无向图，输入1 5 12，默认城市5到城市1也有一条长度为12的路径即可。
- 代码中的p[]可以在有需要时用上，记录的城市i的前驱节点，这样可以依次找到从城市i到起点城市的逆向路径，使用栈逆序即可求出起点到各个顶点最短路径的路线了。
算法分析
- 时间复杂度：O(n^2)
- 最多只出现了两重循环且长度为n
- 空间复杂度：O(n)
- 辅助空间包括一维数组flag[]，i，j，t，temp
算法优化拓展
- 使用优先队列优化
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
const int N = 100;//城市数量
const int INF = 1e7;//初始化无穷大值
int map[N][N], dist[N], p[N], n, m;//n为城市的个数，m为城市间路线的条数
bool flag[N];//flag[i]为true，表明顶点i已加入到集合S
struct Node
{
int u,step;
Node(){};
Node(int a, int sp)
{
u = a;
step = sp;
}
bool operator < (const Node& a)const //重载 <
{
return step > a.step;
}
};
void Dijkstra(int u)
{
priority_queue <Node> Q; //优先队列优化
Q.push(Node(u, 0));
memset(flag, 0, sizeof(flag));//初始化flag数组为0
for(int i=1; i<=n; i++)
dist[i] = INF; //初始化所有距离为无限大
dist[u] = 0;
while(!Q.empty())
{
Node it = Q.top(); //优先队列对头元素为最小值
Q.pop();
int t = it.u;
if(flag[t]) //说明已经找到了最短距离，该节点是队列里面的重复元素
continue;
flag[t] = true;
for(int i=1; i<=n; i++)
{
if(!flag[i]&&map[t][i]<INF)
{
if(dist[i]>dist[t]+map[t][i])
{
//求距离当前点的每个点的最短距离，进行松弛操作
dist[i] = dist[t] + map[t][i];
Q.push(Node(i, dist[i]));//把更新后的最短距离压入优先队列，里面会有重复元素
}
}
}
}
}
int main()
{
int u, v, w, st;
cout << "请输入城市的个数：" << endl;
cin >> n;
cout << "请输入城市之间路线的条数：" << endl;
cin >> m;
cout << "请输入城市之间的路线以及距离：" << endl;
for(int i=1; i<=n; i++)//初始化邻接矩阵
for(int j=1; j<=n; j++)
map[i][j] = INF;//初始化邻接矩阵为无限大
while(m--)
{
cin >> u >> v >> w;
map[u][v] = min(map[u][v], w);//保留最小距离
}
cout << "请输入当前所在位置：" << endl;
cin >> st;
Dijkstra(st);
cout << "起点所在位置：" << st << endl;
for(int i=1; i<=n; i++)
{
cout << "起点：" << st << " - " << "目的地：" << i << " ";
if(dist[i] == INF)
cout << "无法到达" << endl;
else
cout << "最短距离为：" << dist[i] << endl;
}
return 0;
}
- 时间复杂度
- while(!Q.empty()) 的执行次数为n，因为要弹出n个最小值队列才会为空
- Q.pop()的时间复杂度为logn，while语句中的for语句执行n次，for语句中的Q.push()时间复杂度为logn
- 因此，总的语句执行次数为nlogn+(n^2)logn，算法的时间复杂度为O((n^2)logn)
- 看似时间复杂度变大了，是因为采用的是邻接矩阵，如果采用邻接表，for语句的松弛操作就不用每次执行n次了，而是边的数量x，而每个节点的边加起来为E，总的时间复杂度为O(nlogn+Elogn)，当E>n时，时间复杂度为O(E*logn)。
