求带权有向图M中顶点v到其他各个顶点的最短路径C语言-DPDK中文网

以下是一个使用C语言实现的求带权有向图中某个顶点v到其他各个顶点的最短路径的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX 100
#define INFINITY 9999

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_VERTEX][MAX_VERTEX];
    int distance[MAX_VERTEX];
    bool visited[MAX_VERTEX];
    int numVertices;
} Graph;

void initGraph(Graph *graph, int numVertices) {
    graph->numVertices = numVertices;
    
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph->edges[i][j].vertex = -1;
            graph->edges[i][j].weight = INFINITY;
        }
        
        graph->distance[i] = INFINITY;
        graph->visited[i] = false;
    }
}

void addEdge(Graph *graph, int src, int dest, int weight) {
    graph->edges[src][dest].vertex = dest;
    graph->edges[src][dest].weight = weight;
}

int getMinDistance(Graph *graph) {
    int minDistance = INFINITY;
    int minVertex = -1;

    for (int v = 0; v < graph->numVertices; v++) {
        if (!graph->visited[v] && graph->distance[v] <= minDistance) {
            minDistance = graph->distance[v];
            minVertex = v;
        }
    }

    return minVertex;
}

void dijkstra(Graph *graph, int startVertex) {
     // 初始化起始顶点的距离为0
    graph->distance[startVertex] = 0;
    
    for (int i = 0; i < graph->numVertices - 1; i++) {
        int u = getMinDistance(graph);
        graph->visited[u] = true;
        
        // 更新从起始顶点到未访问顶点的最短距离
        for (int v = 0; v < graph->numVertices; v++) {
            if (!graph->visited[v] && graph->edges[u][v].vertex != -1) {
                int newDistance = graph->distance[u] + graph->edges[u][v].weight;
                if (newDistance < graph->distance[v]) {
                    graph->distance[v] = newDistance;
                }
            }
        }
    }
}

int main() {
    Graph graph;
    int numVertices, startVertex;

    printf("Enter the number of vertices in the graph: ");
    scanf("%d", &numVertices);

    initGraph(&graph, numVertices);

    int numEdges;
    printf("Enter the number of edges in the graph: ");
    scanf("%d", &numEdges);

    for (int i = 0; i < numEdges; i++) {
        int src, dest, weight;
        printf("Enter edge %d source, destination and weight: ", i+1);
        scanf("%d %d %d", &src, &dest, &weight);
        addEdge(&graph, src-1, dest-1, weight); // 将输入的索引从1开始转换为从0开始
    }

    printf("Enter the start vertex: ");
    scanf("%d", &startVertex);

    dijkstra(&graph, startVertex-1); // 将输入的索引从1开始转换为从0开始

    printf("Shortest distances from vertex %d:\n", startVertex);
    for (int i = 0; i < graph.numVertices; i++) {
        printf("Vertex %d: ", i+1);
        if (graph.distance[i] == INFINITY) {
            printf("Not reachable\n");
        } else {
            printf("%d\n", graph.distance[i]);
        }
    }

    return 0;
}

这是一个使用Dijkstra算法求解最短路径的示例，通过输入图的顶点数、边数和具体的边信息，以及起始顶点，可以得到该顶点到其他各个顶点的最短距离。请注意，在此示例中，顶点索引从1开始。

内容由零声教学AI助手提供，问题来源于学员提问