基本思想
- 假定一個(gè)源點(diǎn)u，頂點(diǎn)集合V被劃分成兩個(gè)部分：集合 S 和集合 V-S 。
- 初始時(shí)S僅包含源點(diǎn)u，S中的頂點(diǎn)到源點(diǎn)u的最短距離已經(jīng)確定，V-S中的頂點(diǎn)到源點(diǎn)u的最短距離待定。
- 用數(shù)組dist[]記錄每個(gè)頂點(diǎn)到源點(diǎn)u的最短距離。
算法流程
- 數(shù)據(jù)結(jié)構(gòu)：設(shè)地圖的帶權(quán)鄰接矩陣為map[][]，如果源點(diǎn)u到頂點(diǎn)i有邊，則map[u][i]為<u,i>的權(quán)值，否則map[u][i]為∞。利用一位數(shù)組dist[i]記錄頂點(diǎn)i到源點(diǎn)u的最短路徑。
- 初始化， 令集合S = {u}，對(duì)于集合V-S中的所有頂點(diǎn)i，初始化dist[i]=map[u][i]。如果源點(diǎn)u與頂點(diǎn)i有邊相連，初始化p[i]=u，否則p[i]=-1，p[]用來(lái)記錄當(dāng)前頂點(diǎn)i的前驅(qū)節(jié)點(diǎn)。
- 找最小，在集合V-S中依照貪心策略來(lái)尋找使得dist[j]具有最小值的頂點(diǎn)t，即dist[t]=min(dist[j] | j屬于V-S集合)，那么頂點(diǎn)t就是此時(shí)V-S中距離源點(diǎn)u最近的頂點(diǎn)。
- 將t加入S集合， 同時(shí)更新V-S集合，也要更新與頂點(diǎn)t相連的其他頂點(diǎn)到源點(diǎn)u的距離。假設(shè)V-S集合中的頂點(diǎn)j與剛加入到S集合中的頂點(diǎn)t有邊權(quán)值為map[t][i]，如果dist[j] > dist[t] + map[t][i]，則dist[j] = dist[t] + map[t][i]，且更新頂點(diǎn)j的前驅(qū)p[j]=t，否則dist[j]保持不變。
- 判斷集合S-V是否為空，若為空了，結(jié)束算法，否則跳轉(zhuǎn)第3步。
最終dist[]數(shù)組記錄了每個(gè)頂點(diǎn)到源點(diǎn)u的最短距離。
p[j]記錄了頂點(diǎn)j到源點(diǎn)u的最短路徑上的前驅(qū)節(jié)點(diǎn)，通過(guò)p[]能找到頂點(diǎn)j到源點(diǎn)u最短路徑的路線。
一個(gè)簡(jiǎn)單的例子
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 100;//城市數(shù)量
const int INF = 1e7;//初始化無(wú)窮大值
int map[N][N], dist[N], p[N], n, m;//n為城市的個(gè)數(shù)，m為城市間路線的條數(shù)
bool flag[N];//flag[i]為true，表明頂點(diǎn)i已加入到集合S
void Dijkstra(int u)
{
for(int i=1; i<=n; i++)
{
dist[i] = map[u][i];//初始化源點(diǎn)u到各個(gè)頂點(diǎn)的距離
flag[i] = false;
if(dist[i] == INF)
p[i] = -1;//源點(diǎn)u到該頂點(diǎn)的距離無(wú)窮大，說(shuō)明i點(diǎn)與源點(diǎn)不相鄰
else
p[i] = u;
}
dist[u] = 0;
flag[u] = true;//初始化時(shí)，集合S中只有一個(gè)元素，即源點(diǎn)u
for(int i=1; i<=n; i++)
{
int temp = INF, t = u;
for(int j=1; j<=n; j++)//在集合V-S中尋找距離源點(diǎn)u最近的頂點(diǎn)t
{
if(!flag[j]&&dist[j]<temp)
{
t = j;
temp = dist[j];
}
}
if(t==u) return;//找不到t，跳出循環(huán)
flag[t] = true;//否則將t加入S集合
for(int j=1; j<=n; j++)//更新集合V-S中與t相鄰的頂點(diǎn)到源點(diǎn)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 << "請(qǐng)輸入城市的個(gè)數(shù)：" << endl;
cin >> n;
cout << "請(qǐng)輸入城市之間路線的條數(shù)：" << endl;
cin >> m;
cout << "請(qǐng)輸入城市之間的路線以及距離：" << endl;
for(int i=1; i<=n; i++)//初始化鄰接矩陣
for(int j=1; j<=n; j++)
map[i][j] = INF;//初始化鄰接矩陣為無(wú)限大
while(m--)
{
cin >> u >> v >> w;
map[u][v] = min(map[u][v], w);//保留最小距離
}
cout << "請(qǐng)輸入當(dāng)前所在位置：" << endl;
cin >> st;
Dijkstra(st);
cout << "起點(diǎn)所在位置：" << st << endl;
for(int i=1; i<=n; i++)
{
cout << "起點(diǎn)：" << st << " - " << "目的地：" << i << " ";
if(dist[i] == INF)
cout << "無(wú)法到達(dá)" << endl;
else
cout << "最短距離為：" << dist[i] << endl;
}
return 0;
}
輸入和輸出
請(qǐng)輸入城市的個(gè)數(shù)：
5
請(qǐng)輸入城市之間路線的條數(shù)：
11
請(qǐng)輸入城市之間的路線以及距離：
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
請(qǐng)輸入當(dāng)前所在位置：
5
起點(diǎn)所在位置：5
起點(diǎn)：5 - 目的地：1 最短距離為：8
起點(diǎn)：5 - 目的地：2 最短距離為：24
起點(diǎn)：5 - 目的地：3 最短距離為：23
起點(diǎn)：5 - 目的地：4 最短距離為：30
起點(diǎn)：5 - 目的地：5 最短距離為：0
- 城市之間的距離是用有向圖來(lái)表示的，路徑表示都是單向的，如上面輸入的1 5 12，是指城市1到城市5有一條路長(zhǎng)度為12，不代表城市5到城市1有路可走。
- 若要表示無(wú)向圖，輸入1 5 12，默認(rèn)城市5到城市1也有一條長(zhǎng)度為12的路徑即可。
- 代碼中的p[]可以在有需要時(shí)用上，記錄的城市i的前驅(qū)節(jié)點(diǎn)，這樣可以依次找到從城市i到起點(diǎn)城市的逆向路徑，使用棧逆序即可求出起點(diǎn)到各個(gè)頂點(diǎn)最短路徑的路線了。
算法分析
- 時(shí)間復(fù)雜度：O(n^2)
- 最多只出現(xiàn)了兩重循環(huán)且長(zhǎng)度為n
- 空間復(fù)雜度：O(n)
- 輔助空間包括一維數(shù)組flag[]，i，j，t，temp
算法優(yōu)化拓展
- 使用優(yōu)先隊(duì)列優(yōu)化
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
const int N = 100;//城市數(shù)量
const int INF = 1e7;//初始化無(wú)窮大值
int map[N][N], dist[N], p[N], n, m;//n為城市的個(gè)數(shù)，m為城市間路線的條數(shù)
bool flag[N];//flag[i]為true，表明頂點(diǎn)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; //優(yōu)先隊(duì)列優(yōu)化
Q.push(Node(u, 0));
memset(flag, 0, sizeof(flag));//初始化flag數(shù)組為0
for(int i=1; i<=n; i++)
dist[i] = INF; //初始化所有距離為無(wú)限大
dist[u] = 0;
while(!Q.empty())
{
Node it = Q.top(); //優(yōu)先隊(duì)列對(duì)頭元素為最小值
Q.pop();
int t = it.u;
if(flag[t]) //說(shuō)明已經(jīng)找到了最短距離，該節(jié)點(diǎn)是隊(duì)列里面的重復(fù)元素
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])
{
//求距離當(dāng)前點(diǎn)的每個(gè)點(diǎn)的最短距離，進(jìn)行松弛操作
dist[i] = dist[t] + map[t][i];
Q.push(Node(i, dist[i]));//把更新后的最短距離壓入優(yōu)先隊(duì)列，里面會(huì)有重復(fù)元素
}
}
}
}
}
int main()
{
int u, v, w, st;
cout << "請(qǐng)輸入城市的個(gè)數(shù)：" << endl;
cin >> n;
cout << "請(qǐng)輸入城市之間路線的條數(shù)：" << endl;
cin >> m;
cout << "請(qǐng)輸入城市之間的路線以及距離：" << endl;
for(int i=1; i<=n; i++)//初始化鄰接矩陣
for(int j=1; j<=n; j++)
map[i][j] = INF;//初始化鄰接矩陣為無(wú)限大
while(m--)
{
cin >> u >> v >> w;
map[u][v] = min(map[u][v], w);//保留最小距離
}
cout << "請(qǐng)輸入當(dāng)前所在位置：" << endl;
cin >> st;
Dijkstra(st);
cout << "起點(diǎn)所在位置：" << st << endl;
for(int i=1; i<=n; i++)
{
cout << "起點(diǎn)：" << st << " - " << "目的地：" << i << " ";
if(dist[i] == INF)
cout << "無(wú)法到達(dá)" << endl;
else
cout << "最短距離為：" << dist[i] << endl;
}
return 0;
}
- 時(shí)間復(fù)雜度
- while(!Q.empty()) 的執(zhí)行次數(shù)為n，因?yàn)橐獜棾鰊個(gè)最小值隊(duì)列才會(huì)為空
- Q.pop()的時(shí)間復(fù)雜度為logn，while語(yǔ)句中的for語(yǔ)句執(zhí)行n次，for語(yǔ)句中的Q.push()時(shí)間復(fù)雜度為logn
- 因此，總的語(yǔ)句執(zhí)行次數(shù)為nlogn+(n^2)logn，算法的時(shí)間復(fù)雜度為O((n^2)logn)
- 看似時(shí)間復(fù)雜度變大了，是因?yàn)椴捎玫氖青徑泳仃嚕绻捎绵徑颖?，for語(yǔ)句的松弛操作就不用每次執(zhí)行n次了，而是邊的數(shù)量x，而每個(gè)節(jié)點(diǎn)的邊加起來(lái)為E，總的時(shí)間復(fù)雜度為O(nlogn+Elogn)，當(dāng)E>n時(shí)，時(shí)間復(fù)雜度為O(E*logn)。
