用c++写出一个最短路算法

以下是Dijkstra算法的C代码实现：

#include <stdio.h>
#include <limits.h>

#define V 6 // 图的顶点数
#define INF INT_MAX // 无穷大

int graph[V][V] = { // 图的邻接矩阵
    {0, 2, 4, 0, 0, 0},
    {2, 0, 1, 4, 2, 0},
    {4, 1, 0, 0, 3, 0},
    {0, 4, 0, 0, 3, 2},
    {0, 2, 3, 3, 0, 2},
    {0, 0, 0, 2, 2, 0}
};

void dijkstra(int start) {
    int dist[V]; // 存储起点到每个顶点的最短距离
    int visited[V] = {0}; // 标记顶点是否已经访问过
    
    // 初始化距离数组
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
    }
    dist[start] = 0; // 起点到自己的距离为0
    
    for (int i = 0; i < V - 1; i++) { // 执行V-1次循环
        int u = -1;
        for (int v = 0; v < V; v++) { // 找到距离起点最近的未访问顶点
            if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
                u = v;
            }
        }
        
        visited[u] = 1; // 标记该顶点为已访问
        for (int v = 0; v < V; v++) { // 更新起点到其他顶点的距离
            if (graph[u][v] != 0 && !visited[v]) {
                int newdist = dist[u] + graph[u][v];
                if (newdist < dist[v]) {
                    dist[v] = newdist;
                }
            }
        }
    }
    
    // 输出结果
    printf("起点到其他顶点的最短距离为：\n");
    for (int i = 0; i < V; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
}

int main() {
    dijkstra(0); // 以0号顶点为起点执行Dijkstra算法
    return 0;
}

该算法采用了贪心策略，每次找到距离起点最近的未访问顶点，并更新起点到其他顶点的距离。时间复杂度为O(V^2)，其中V为图的顶点数。