最短路径算法c语言

最短路径算法主要有 Dijkstra、Bellman-Ford、Floyd 三种，下面我为您提供一份 Dijkstra 算法的 C 语言实现代码。

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

#define MAX_VERTICES 1000
#define INF INT_MAX

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

int get_min_vertex() {
    int v, min_v = 0;
    for (v = 0; v < num_vertices; v++) {
        if (!visited[v]) {
            min_v = v;
            break;
        }
    }
    for (v = 0; v < num_vertices; v++) {
        if (!visited[v] && dist[v] < dist[min_v]) {
            min_v = v;
        }
    }
    return min_v;
}

void dijkstra(int start) {
    int v, u;
    for (v = 0; v < num_vertices; v++) {
        dist[v] = INF;
    }
    dist[start] = 0;
    for (v = 0; v < num_vertices; v++) {
        u = get_min_vertex();
        visited[u] = 1;
        for (v = 0; v < num_vertices; v++) {
            if (graph[u][v] && !visited[v]) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
}

int main() {
    int i, j, start;
    scanf("%d", &num_vertices);
    for (i = 0; i < num_vertices; i++) {
        for (j = 0; j < num_vertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    scanf("%d", &start);
    dijkstra(start);
    for (i = 0; i < num_vertices; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
    return 0;
}

注意：该代码实现的是针对正权值的最短路径算法，如果有负权值需要使用 Bellman-Ford 或 Floyd 算法。