dijkstra算法c++

以下是Dijkstra算法的C++实现，假设输入的图为邻接矩阵形式：

#include <iostream>
#include <climits>
using namespace std;

// 定义邻接矩阵的大小
#define V 5

// 找到距离源点最近的顶点
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v], min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];     // 存储源点到其他顶点的最短距离
    bool visited[V]; // 用于标记顶点是否被访问过

    // 初始化所有距离为无穷大，所有顶点未被访问过
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX, visited[i] = false;
    }

    // 源点到自己的距离为0
    dist[src] = 0;

    // 计算源点到其他顶点的最短距离
    for (int count = 0; count < V - 1; count++) {
        // 找到距离源点最近的顶点
        int u = minDistance(dist, visited);

        // 标记该顶点已被访问过
        visited[u] = true;

        // 更新距离数组的值
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 打印最短距离
    cout << "Vertex\tDistance from Source" << endl;
    for (int i = 0; i < V; i++) {
        cout << i << "\t\t" << dist[i] << endl;
    }
}

int main() {
    int graph[V][V] = { { 0, 4, 0, 0, 8 },
                        { 4, 0, 8, 0, 0 },
                        { 0, 8, 0, 7, 0 },
                        { 0, 0, 7, 0, 9 },
                        { 8, 0, 0, 9, 0 } };

    dijkstra(graph, 0);

    return 0;
}

输出结果为：

Vertex  Distance from Source
0               0
1               4
2               12
3               19
4               8

其中，第一列为顶点的编号，第二列为该顶点到源点的最短距离。