C++ 中的 Dijkstra 算法

Dijkstra算法是一种经典的图算法，用于求解带权有向图中的单源最短路径问题。该算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出，被广泛应用于网络路由、地图导航、城市规划等领域。本文将介绍Dijkstra算法的原理和实现，并通过一个简单的案例来演示其应用。

       4       2
   0 ------? 1 ------? 3
   |         ▲
   |         |
   |5        |3
   ▼         |
   2 ------? 4
       6

cpp
#include 
#include 
#include 
using namespace std;
const int INF = INT_MAX;
vector dijkstra(vector>& graph, int source) {
    int n = graph.size();
    vector dist(n, INF);
    vector visited(n, false);
    dist[source] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    return dist;
}
int main() {
    vector> graph = {
        {0, 4, INF, INF, 2},
        {INF, 0, 2, INF, INF},
        {INF, INF, 0, 3, INF},
        {INF, INF, INF, 0, INF},
        {INF, INF, INF, 6, 0}
    };
    vector shortestDist = dijkstra(graph, 0);
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "Shortest distance from 0 to " << i << " is " << shortestDist[i] << endl;
    }
    return 0;
}