(3)设计Dijkstra算法并在VC下用C语言实现算法

算法描述：

1. 创建一个空的距离表dist[]和一个空的已访问节点集合visited[]，将起点的距离设置为0，将起点加入已访问节点集合。

2. 从起点开始，按照距离从小到大的顺序遍历所有与该节点相邻的未访问节点，计算它们到起点的距离，并更新距离表dist[]。

3. 在所有未访问节点中选取距离起点最近的节点，并将其加入已访问节点集合。

4. 重复步骤2和3，直到所有节点都被访问。

C语言实现：

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

#define MAX_VERTICES 100

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

int dijkstra(int graph[][MAX_VERTICES], int num_vertices, int start, int end, int path[]) {
    Edge dist[MAX_VERTICES];
    int i, j, min_dist, next_node;

    for (i = 0; i < num_vertices; i++) {
        dist[i].weight = INT_MAX;  
        dist[i].visited = 0;       
        path[i] = -1;               
    }

    dist[start].weight = 0;  
    dist[start].visited = 1; 

    for (i = 0; i < num_vertices; i++) {
        min_dist = INT_MAX;
        for (j = 0; j < num_vertices; j++) {
            if (!dist[j].visited && dist[j].weight < min_dist) {
                min_dist = dist[j].weight;
                next_node = j;
            }
        }
        if (min_dist == INT_MAX) break;  
        dist[next_node].visited = 1;
        for (j = 0; j < num_vertices; j++) {
            if (!dist[j].visited && graph[next_node][j] != 0 && dist[next_node].weight + graph[next_node][j] < dist[j].weight) {
                dist[j].weight = dist[next_node].weight + graph[next_node][j];
                path[j] = next_node;
            }
        }
    }

    return dist[end].weight;
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES];
    int num_vertices, num_edges, i, j, start, end, weight;
    int path[MAX_VERTICES];

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

    printf("Enter the number of edges: ");
    scanf("%d", &num_edges);

    for (i = 0; i < num_vertices; i++) {
        for (j = 0; j < num_vertices; j++) {
            graph[i][j] = 0;
        }
    }

    for (i = 0; i < num_edges; i++) {
        printf("Enter edge %d: ", i + 1);
        scanf("%d %d %d", &start, &end, &weight);
        graph[start][end] = weight;
    }

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

    printf("Enter the ending vertex: ");
    scanf("%d", &end);

    int shortest_path = dijkstra(graph, num_vertices, start, end, path);

    printf("Shortest path from %d to %d: %d\n", start, end, shortest_path);

    printf("Path: ");
    int p = end;
    while (p != -1) {
        printf("%d ", p);
        p = path[p];
    }
    printf("\n");

    return 0;
}