本文共 2787 字，大约阅读时间需要 9 分钟。

Dijkstra算法总结

目的

求一个带权有向图中某个定点到其他各个顶点的最短路径，解决单源图的最短路径问题。

要求

思想

以泰坦尼克号撞冰山后的救生问题为例，描述了如何通过关系优先度来选择下一个需要救的人。这个过程需要两个名单来记录：一个记录各个落水者与“你”的关系程度，另一个记录救起各个落水者的人员。

手动实现

以2016年计算机联考真题为例，给出图示并手动模拟Dijkstra算法的运行过程：

• 初始化时，源点1的距离为0，其他点的距离设为无穷大。
• 初始时，s集合包含源点1。
• 每次从s集合中选出一个满足dist最小的点，例如点5，加入s集合。
• 更新其他点的距离，例如点6的距离被更新为4。
• 重复上述过程，直到所有点都被加入s集合。

时间复杂度

Dijkstra算法的时间复杂度为O(|v|²)，其中|v|为所有顶点数。当把各个点都看成顶点进行算法执行时，时间复杂度为O(|v|³)。

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
#define INF 65535
#define Max 5
void Dijkstra(int arcs[][Max+1], int n, int v0) {
    int path[n+1];
    int dist[n+1];
    int s[n+1] = {1}; // 初始化，s[0]记录旧集合开始的下标
    int i, j, k, min = INF, temp, v1;
    bool change = true;
    for (i = 1; i <= n; i++) {
        dist[i] = arcs[v0][i];
        s[i] = i;
    }
    swap(s[1], s[v0]);
    v1 = v0;
    path[v0] = -1;
    while (s[0] != n+1 && change) {
        change = false;
        min = dist[s[s[0]]];
        temp = s[0];
        i = s[0];
        while (i <= n) {
            if (dist[s[i]] < min) {
                min = dist[s[i]];
                temp = s[i];
            }
            i++;
        }
        j = s[0];
        while (s[j] != temp) {
            j++;
        }
        if (j != s[0]) {
            swap(s[s[0]], s[j]);
            s[0]++;
            if (s[0] == n+1) break;
            path[temp] = (v1 == v0) ? v1 : path[temp];
            change = true;
        }
        temp = s[s[0]];
        while (i <= n) {
            if (dist[i] > dist[temp] + arcs[temp][i]) {
                dist[i] = dist[temp] + arcs[temp][i];
                path[i] = temp;
            }
            i++;
        }
        v1 = temp;
    }
}
int main() {
    int arcs[Max+1][Max+1];
    for (int i = 0; i <= Max; i++) {
        for (int j = 0; j <= Max; j++) {
            arcs[i][j] = INF;
        }
    }
    arcs[1][2] = 10;
    arcs[1][5] = 5;
    arcs[2][3] = 1;
    arcs[2][5] = 2;
    arcs[3][4] = 6;
    arcs[4][1] = 7;
    arcs[4][3] = 6;
    arcs[5][2] = 3;
    arcs[5][3] = 9;
    arcs[5][4] = 2;
    int n = 5;
    int v0 = 1;
    Dijkstra(arcs, n, v0);
    cout << "集合S：" << endl;
    for (int i = 1; i <= n; i++) {
        cout << pp[n*2 + i] << " ";
    }
    cout << endl << "最短路径：" << endl;
    for (int i = 2; i <= n; i++) {
        int j = pp[n*2 + i];
        cout << "第" << (i-1) << "趟: ";
        while (j != 1) {
            ss.push(j);
            j = path[j];
        }
        ss.push(j);
        while (!ss.empty()) {
            int node = ss.top();
            ss.pop();
            if (node == 1) break;
            cout << node << " ";
        }
    }
    return 0;
}
     
    
   

参考文献