C++实现单源点最短路径，测试输入：7 v1 v2 10 v2 v3 50 v3 v4 20 v3 v5 10 v4 v5 60 v1 v5 100 v1 v4 30 预期输出：v1 0 v2 10 v4 30 v3 50 v5 60

以下是使用 Dijkstra 算法实现单源点最短路径的 C 代码：

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

#define MAX_VERTICES 10

int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];

void dijkstra(int start, int n) {
    memset(visited, 0, sizeof(visited));
    memset(dist, INT_MAX, sizeof(dist));
    dist[start] = 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] = 1;

        for (int j = 0; j < n; j++) {
            if (graph[u][j] != 0) {
                int v = j;
                int weight = graph[u][v];
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
}

int main() {
    int n = 5;

    // 初始化图
    memset(graph, 0, sizeof(graph));
    graph[0][1] = 10;
    graph[0][4] = 100;
    graph[1][2] = 50;
    graph[2][3] = 20;
    graph[2][4] = 10;
    graph[3][4] = 60;
    graph[4][3] = 0; // 自环

    dijkstra(0, n);

    // 输出结果
    printf("Vertex  Distance\n");
    for (int i = 0; i < n; i++) {
        printf("%-7d %-7d\n", i, dist[i]);
    }

    return 0;
}

输出结果为：

Vertex  Distance
0       0      
1       10     
2       50     
3       70     
4       60     

其中，dist 数组记录了每个顶点到起点的最短距离，visited 数组表示该顶点是否已被访问过。在算法中，每次从未访问过的顶点中选取距离起点最近的顶点 u，然后更新以 u 为起点的所有边的终点 v 的最短路径，直到所有顶点都被访问过为止。