一.算法描述
Dijkstra算法的流程如下：
1.初始化dist[1] = 0，其余節(jié)點(diǎn)的dist值為無(wú)窮大。
2.找出一個(gè)未被標(biāo)記的、dist[x]最小的節(jié)點(diǎn)x，然后標(biāo)記節(jié)點(diǎn)x。
3.掃描節(jié)點(diǎn)x的所有出邊（x，y，z），若dist[y] > dist[x] + z，則使用dist[x] + z更新dist[y]。
4.重復(fù)上述2~3兩個(gè)步驟，直到所有的節(jié)點(diǎn)都被標(biāo)記。
Dijkstra算法基于貪心思想，它只適用于所有邊的長(zhǎng)度都是非負(fù)整數(shù)的圖。當(dāng)邊長(zhǎng)都是負(fù)數(shù)時(shí)，全局的最小值不可能在被其他節(jié)點(diǎn)更新，故在第一步中選出的節(jié)點(diǎn)x必然滿(mǎn)足：dist[x]已經(jīng)是起點(diǎn)到x的最短路徑。我們不斷選擇全局最小值進(jìn)行標(biāo)記和擴(kuò)展，最終得到起點(diǎn)1到每個(gè)節(jié)點(diǎn)的最短路徑長(zhǎng)度。
二.算法應(yīng)用
例:對(duì)于如下有向圖求1 號(hào)點(diǎn)到 4 號(hào)點(diǎn)的最短距離
(1).初始狀態(tài)原點(diǎn)到1號(hào)的距離為0,因此dist[1] = 0
(2).遍歷dist數(shù)組找到當(dāng)前距離原點(diǎn)最近的點(diǎn)i并將該點(diǎn)進(jìn)行標(biāo)記,用找到的點(diǎn)i更新i能到的所有點(diǎn)的距離j,如果 dist[j] 大于 dist[i] 加上 i -> j 的距離，即 dist[j] > dist[i] + w[i][j]（w[i][j] 為 i -> j 的距離） ，則更新 dist[j] = dist[i] + w[i][j]
(3).重復(fù)步驟(2),直到所有的點(diǎn)都被標(biāo)記為1
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-460869.html
三.代碼示例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N], dist[N];
int n, m;
bool st[N];
int dijkstra()
{
dist[1] = 0;
for(int i = 0; i < n; i++)
{
int t = -1;
//找到未標(biāo)記節(jié)點(diǎn)中dist最小的
for(int j = 1; j <= n; j++)
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
//用全局最小的值點(diǎn)t更新其他點(diǎn)
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
memset(dist, 0x3f, sizeof dist);
//構(gòu)建鄰接矩陣
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);
}
//求單源最短路徑
dijkstra();
for(int i = 1; i <= n; i++) printf("%d\n", dist[i]);
return 0;
}
四.算法改進(jìn)
Dijkstra算法的時(shí)間復(fù)雜度為O(n^2)，主要的瓶頸在于第一步的尋找全局最小值的過(guò)程?？梢杂枚娑眩–++ STL priority_queue）對(duì)dist數(shù)組進(jìn)行維護(hù)，用O(longn)的時(shí)間獲取最小值并從堆中刪除。用O(longn)的時(shí)間執(zhí)行一條邊的擴(kuò)展和更新，最終可在O(mlongn)的時(shí)間內(nèi)實(shí)現(xiàn)Dijkstra算法。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-460869.html
堆優(yōu)化版的Dijkstra算法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int h[N], e[N], ne[N], w[N], idx; //鄰接表
int dist[N];
bool st[N]; //標(biāo)記數(shù)組
//構(gòu)建鄰接表
void add(int a, int b,int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//pair的第一維為當(dāng)前節(jié)點(diǎn)到原點(diǎn)的最短距離，第二維為節(jié)點(diǎn)編號(hào)
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({dist[1], 1});
while(heap.size())
{
//取出堆頂
auto k = heap.top();
heap.pop();
int ver = k.y, distance = k.x;
if(st[ver]) continue;
st[ver] = true;
//掃描所有出邊
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
//更新，把新的二元組插入堆
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
//構(gòu)建鄰接表
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra();
return 0;
}
}
到了這里，關(guān)于Dijkstra算法求最短路的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
