Dijkstra

本文最后更新于:12 天前

源代码

#include<bits/stdc++.h>

static int INF = INT_MAX;

/**
 * 
 * @param n 节点个数
 * @param src 起点
 * @param w[][] 邻接矩阵
 * @param vis[] 是否被访问过
 * @param dist[] 从src到n的最短路径
 */
void Dijkstra(int n, int src, vector<vector<int>> &w, vector<bool> &vis, vector<int> &dist) {
    // 初始化
    // 全部设置为未访问过
    fill(vis.begin(), vis.end(), false);
    fill(dist.begin(), dist.end(), INF);
    dist[src] = 0;

    for (int i = 0; i < n; ++i) {
        // 在未访问过的节点中选择路径最短的一个
        int min_index = -1;
        int MIN = INF;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && dist[j] < MIN) {
                min_index = j;
                MIN = dist[j];
            }
        }
        // 没有找到最小 return
        if (min_index == -1) return;
        // 找到最小,设置为已被访问
        vis[min_index] = true;
        // 更新 从src 经过 上一步选择出的最小的节点 到达 dist[v] 的距离
        for (int v = 0; v < n; ++v) {
            // 未被访问 && 可到达 && 路径更短
            // 经过 min_index ,从 src 到 v 的路径更短 -> 更新
            if (!vis[v] && w[min_index][v] != INF && dist[min_index] + w[min_index][v] < dist[v]) {
                // 更新路径
                dist[v] = dist[min_index] + w[min_index][v];
            }
        }
    }
    // 打印结果
    cout << "dist[]: ";
    for (int i: dist) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    int n = 5;
    vector<vector<int>> w = {
            {0,   10,  3,   INF, INF},
            {INF, 0,   1,   2,   INF},
            {INF, 4,   0,   8,   2},
            {INF, INF, INF, 0,   7,},
            {INF, INF, INF, 9,   0,}
    };
    // 是否被访问过
    vector<bool> vis(n);
    vector<int> dist(n);

    Dijkstra(n, 0, w, vis, dist);

    return 0;
}

运行结果

image-20211026163623195


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!