Dijkstra演算法只能求取邊的權重為非負的圖的最短路徑，而Bellman-Ford演算法可以求取邊的權重為負的圖的最短路徑（但Bellman-Ford演算法在圖中存在負環的情況下，最短路徑是不存在的（負無窮）），
演算法原理
Dijkstra演算法本質上是一種貪心演算法，1959年，Edsger Dijkstra提出了該演算法用于解決單源最短路徑問題，即在給定每條邊的長度\(\mathcal{l}\)，求取源節點s到其它所有節點的最短路徑，Dijkstra演算法維護一個節點集合S，S中的節點到源點的最短距離d已經確定了，即“Explored”，
初始化時，\(S={s},d(s)=0\)，接下來開始回圈，對于每一個節點\(v\in V-S\)，選出到集合S的距離最近的節點\(v^*\)，即最小化下面這個問題：
\begin{equation}
d'(v)=\min_{e=(u,v):u\in S}d(u)+\mathcal{l}_e
\end{equation}
我們將\(v^*\)加入到集合S，并定義\(d(v^*)=d'(v^*)\)，然后繼續下一次回圈，
演算法偽代碼如下：
復雜度分析
樸素實作
每次while回圈，將1個節點加入集合S中，所以共n-1次外層回圈，對于一個有m條邊的圖而言，求解式(1)最壞情況下，需要遍歷所有的邊，即需要\(\mathcal{O}(m)\)的時間復雜度，所以程式整體的時間復雜度為\(\mathcal{O}(mn)\)，如果看下文例題中POJ2387的樸素實作，可能會發現演算法復雜度是\(\mathcal{O}(n^2)\)，不是\(\mathcal{O}(mn)\)，但其實在例題中，在輸入時，每兩個節點間只有一條邊相連（如果有多條，則只保留最短的一條），另外，每次將節點v_opt新加入S中時，我們會更新v_opt節點相鄰的節點的\(d'(v)\)的值，并將其存盤在陣列中，從而每次求解式(1)時，我們只需要遍歷非S集合的節點的\(d'(v)\)值，就能得到式(1)的答案，從而降低了求解式(1)的復雜度（降為\(\mathcal{O}(n)\)），整體復雜度降為\(\mathcal{O}(n^2)\)，而對于一般情況，理論上的復雜度就是\(\mathcal{O}(mn)\)，
優先佇列優化
上文中提到將非S集合的節點的\(d'(v)\)值存盤在陣列里，每次遍歷陣列得到式(1)的答案（即\(d'(v)\)的最小值），而這一個地方還可以進一步優化，采取優先佇列存盤非S集合的節點，節點對應的\(d'(v)\)作為鍵值，若采用二叉堆實作優先佇列（可以參考優先佇列及（二叉）堆），每次只需要\(\mathcal{O}(\log n)\)的時間即可求得\(d'(v)\)的最小值（得到最小值后需洗掉該值），
優先佇列實作的偽代碼如下：
例題
POJ2387
典型Dijkstra模板題，需要注意不同landmark(節點)間的路徑可能有多條，這是一個WA點，若用鄰接矩陣存盤圖，解決辦法是只保留最短的一條路徑，若用鄰接表存盤圖，則不需要對重復邊進行特別處理，
樸素實作
用explored陣列來標記是否屬于集合S，外層for回圈共執行n次，每次標記一個節點，回圈內遍歷非S集合的節點，求出到S集合的距離最短的節點v_opt，然后更新與v_opt相鄰的節點\(d'(v)\)（即distance陣列）的值，整體復雜度\(\mathcal{O}(n^2)\)
Result: 4280kB, 125ms. 說起來POJ的Time不是很固定啊，同樣的代碼，上次是63ms，這次是125ms，
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <queue>
int t, n;
int adjacency_matrix[1005][1005];
int distance[1005];
int explored[1005];//標記是否屬于集合S
void DijkstraSimple() {
distance[n] = 0;
for (int i = 1; i <= n; i++) {//每次將一個節點加入S，共回圈n次
int min = 0x3f3f3f3f;
int v_opt;//最小化式(1)的節點
for (int v = 1; v <= n; v++)//找出S集合中最小化式(1)的節點
if (!explored[v] && distance[v] < min) {
min = distance[v];
v_opt = v;
}
explored[v_opt] = 1;
for (int v = 1; v <= n; v++)
if (!explored[v])//v未添加進集合S且v_opt、v之間有邊相連
distance[v] = std::min(distance[v], distance[v_opt] + adjacency_matrix[v_opt][v]);
}
}
int main() {
while (scanf("%d %d", &t, &n) != EOF) {
memset(adjacency_matrix, 0x3f, sizeof(adjacency_matrix));
memset(distance, 0x3f, sizeof(distance));
memset(explored, 0, sizeof(explored));
int u, v, length;
for (int i = 1; i <= t; i++) {
scanf("%d %d %d", &u, &v, &length);
if (adjacency_matrix[u][v] > length) {//兩個landmark之間可能有多條路，這是一個WA點，有多條路時，取length最小的路
adjacency_matrix[u][v] = length;
adjacency_matrix[v][u] = length;
}
}
DijkstraSimple();
printf("%d\n", distance[1]);
}
return 0;
}
優先佇列實作
圖2優先佇列實作的偽代碼中，要求通過decrease_key函式改變特定節點\(v\)的鍵值，但實際上，正如我的優先佇列及（二叉）堆這篇博客中提到的，優先佇列的基本操作并不包含改變特定節點的鍵值，在優先佇列及（二叉）堆庫函式實作小節中，我也提到可以通過維護一個position陣列來實作改變特定節點的鍵值，下列代碼正是基于這種思路實作改變特定節點的鍵值，
Result: 388kB, 16ms; 388kB, 32ms. POJ的Time確實不太穩定，同樣的代碼，隔十分鐘提交的結果就不太一樣，但是相對樸素實作速度提高很多，
/*
自己實作的堆演算法，通過position記錄下元素在堆（陣列）中的位置，可以直接更改特定編號的元素的鍵值
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
//上限
#define N (1000 + 10)
#define M (4000 + 10)//無向圖，應大于邊數量的2倍
#define parent(i) (int)floor(i/2)
#define left(i) i * 2
#define right(i) i * 2 + 1
struct element {
int number;//元素編號
int key;//元素鍵值
element() {}
element(int number, int key) : number(number), key(key) {}
};
element A[N];//存盤最小堆
int position[N];//存盤元素在堆(陣列)中的位置
int min_heap_size;
int explored[N];//標記是否屬于集合S
int distance[N];//距源點的最短距離
int t, n;
struct edge {//通過鏈表存盤邊
int v, length, next;
};
edge e[M];
int head[N];//節點的第一條邊在e陣列中位置
int num_of_edges;
int add_edge(int u, int v, int length1, int length2) {
int& i = num_of_edges;
e[i].v = v;
e[i].length = length1;
e[i].next = head[u];
head[u] = i++;
e[i].v = u;
e[i].length = length2;
e[i].next = head[v];
head[v] = i++;
return i;
}
template<class T> void exchange(element* array, int i, int j) {
position[A[i].number] = j;//交換兩者的位置
position[A[j].number] = i;
T temp = array[i];//交換二者的資料
array[i] = array[j];
array[j] = temp;
}
//最小堆
void heap_decrease_key(int i, int key) {
if (key > A[i].key)
printf("error: new key is bigger than current key.");
A[i].key = key;
while (i > 1 && A[parent(i)].key > A[i].key)
{
exchange<element>(A, i, parent(i));
i = parent(i);
}
}
void min_heap_insert(element elem) {
min_heap_size++;
A[min_heap_size].number = elem.number;
A[min_heap_size].key = 0x3f3f3f3f;
position[elem.number] = min_heap_size;//記錄下位置
heap_decrease_key(min_heap_size, elem.key);
}
element heap_minimum() {
return A[1];
}
void min_heapify(int i) {
int l = left(i), r = right(i);
int smallest = i;
if (l <= min_heap_size && A[l].key < A[i].key)
smallest = l;
if (r <= min_heap_size && A[r].key < A[smallest].key)
smallest = r;
if (smallest != i) {
exchange<element>(A, i, smallest);
min_heapify(smallest);
}
}
element heap_extract_min(void) {
element min = A[1];
position[A[min_heap_size].number] = 1;//heap_size位置的挪到1的位置
A[1] = A[min_heap_size];
min_heap_size--;
min_heapify(1);
return min;
}
void DijkstraPriorityQueue() {
min_heap_insert(element(n, 0));
distance[n] = 0;
for (int i = 1; i < n; i++)//將所有節點都放入優先佇列中
min_heap_insert(element(i, 0x3f3f3f3f));
for (int i = 1; i <= n; i++) {//每次把一個節點從優先佇列中取出加入到S中，外層回圈n次
element front_elem = heap_extract_min();
int u = front_elem.number;
explored[u] = 1;
distance[u] = front_elem.key;
for (int j = head[u]; j >= 0; j = e[j].next) {//遍歷u出發的所有邊
int v = e[j].v;
if (explored[v])
continue;
if (A[position[v]].key > distance[u] + e[j].length)
heap_decrease_key(position[v], distance[u] + e[j].length);
}
}
}
void Init() {
min_heap_size = 0;
memset(position, -1, sizeof(position));
memset(explored, 0, sizeof(explored));
memset(distance, 0x3f, sizeof(distance));
num_of_edges = 0;
memset(head, -1, sizeof(head));
}
int main() {
while (scanf("%d %d", &t, &n) != EOF){
Init();
int u, v, length;
for (int i = 1; i <= t; i++) {
scanf("%d %d %d", &u, &v, &length);
add_edge(u, v, length, length);
}
DijkstraPriorityQueue();
printf("%d\n", distance[1]);
}
return 0;
}
參考：
[1] 演算法設計
[2] 演算法導論
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114573.html
標籤：其他
上一篇：字串
下一篇：復雜度分析