用Dijkstra算法實作最短路徑——C語言

/**
 * @Author: fanzhang
 * @Date: 2019-02-26 19:51:09
 * @Desc:  Dijkstra最短路徑算法
 */
#include <stdio.h>
#include <stdlib.h>
#define Max 1000000
typedef struct
{
    int fromvex, endvex; //邊的起點和終點
    float length;
} edge;
//float dist[][]
void diskstra(int v, float** dist, float* D, int* p, int* s, int n);
void creatadjarry(float** dist, int n, int e);
int main(int argc, char const* argv[])
{
    int e, n, i;
    float** dist; //
    printf("輸入圖的頂點數和邊數:");
    scanf("%d%d", &n, &e);
    dist = (float**)malloc(sizeof(float) * n);
    for (i = 0; i < n; i++)
        dist[i] = (float*)malloc(sizeof(float) * n);
    float* D = (float*)malloc(sizeof(float) * n);
    int* p = (int*)malloc(sizeof(int) * n);
    int* s = (int*)malloc(sizeof(int) * n);
    creatadjarry(dist, n, e);
    diskstra(0, dist, D, p, s, n);
    free(dist);
    free(D);
    free(p);
    free(s);
    return 0;
}
void diskstra(int v, float** dist, float* D, int* p, int* s, int n)
{ //求源點v到其他各點的最短路徑及長度
    int i, j, k, v1, min, max = 10000, pre; //max表示無窮大
    v1 = v;
    for (i = 0; i < n; i++) {
        D[i] = dist[v][i];
        if (D[i] != max)
            p[i] = v1 + 1;
        else
            p[i] = 0;
        s[i] = 0;
    }
    s[v1] = 1; //将源點送入u
    for (i = 0; i < n - 1; i++) {
        min = 10001;
        for (j = 0; j < n - 1; j++)
            if ((!s[j]) && D[j] < min) {
                min = D[j];
                k = j;
            }
        s[k] = 1; //将找到的頂點k送入u
        for (j = 0; j < n; j++)
            if (!s[j] && (D[j] > D[k] + dist[k][j])) {
                D[j] = D[k] + dist[k][j];
                p[j] = k + 1;
            }
    }
    for (i = 0; i < n; i++) { //輸出路徑
        printf("路徑長度: %-6g  路徑: %c", D[i], 'A' + i);
        pre = p[i];
        while ((pre != 0) && (pre != v + 1)) {
            printf(" << %c", 'A' + pre - 1);
            pre = p[pre - 1];
        }
        printf(" << %c", 'A' + v);
        printf("\n");
    }
    printf("\n");
}
void creatadjarry(float** dist, int n, int e) //建立鄰接矩陣
{
    int i, j;
    for (i = 0; i < n; i++) { //賦初值
        for (j = 0; j < n; j++)
            dist[i][j] = Max;
        dist[i][i] = 0;
    }
    for (int a = 0; a < e; a++) {
        printf("輸入第%d條邊的頂點終點和權值:", a + 1);
        scanf("%d%d", &i, &j);
        scanf("%f", &dist[i][j]);
    }
}
           

運作結果