聊一聊利用Dijkstra求有向圖的最短路徑

0x00 前言

我們都知道求最短路徑有很多方法，比如Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法等等，這些算法各有優缺點，其中Floyd-Warshall算法時間複雜度較高，但是編碼複雜度較小，而Bellman-Ford算法适用于處理有負權邊的情況。至于本文要講的Dijkstra算法，優點就是時間複雜度較小，但是不能處理有負權邊的圖。

我們需要根據不同情況選擇不同的算法。

0x01 代碼分析

#include<stdio.h>
#define MAXVEX 10
int graph[MAXVEX][MAXVEX];
int short_path[MAXVEX];
int prev_v[MAXVEX];           

先導入标準輸入輸出庫，我們将節點數設定為10個，然後設定存儲圖的graph、存儲源點到其他各點的最短路徑長度的short_path，還有存儲最短路徑上各節點的前置節點的prev_v。

1. 建圖

void create_graph( void ){
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            if(i==j){
                graph[i][j]=0;
                continue;
            }
            graph[i][j] = 99999;
        }
    }
    printf("請輸入有向邊的條數:");
    int n;
    scanf("%d",&n);
    for(int k=0;k<n;k++){
        int i,j,value;
        scanf("%d %d %d",&i,&j,&value);
        graph[i][j]=value;
    }
}           

然後就是将圖初始化了。這裡我們将沒個頂點到自己的距離初始化為0，然後将其他點先全部初始化為99999，然後在給每條邊賦權值。

2. 求最短路徑

void Dijkstra(int g[10][10], int v0) {
    int final[MAXVEX];
    int j = 0;
    int k = 0;
    for(j = 0; j<MAXVEX; j++) { 
        final[j] = 0;
        short_path[j] = g[v0][j];
        prev_v[j] = 0;
    }
    final[v0] = 1; 
    short_path[v0] = 0;
    
    for(int i = 1; i < MAXVEX; i++) { 
        int min = MAXVEX;
        k = 0;
        for(int j=0; j<MAXVEX; j++) {
            if(final[j]==0 && short_path[j]<min) {
                min = short_path[j];
                k = j;
            }
        }
        final[k] = 1; 
        
        for(int j=0; j<MAXVEX; j++) {
            if(final[j]==0 && min+g[k][j] < short_path[j]) {
                short_path[j] = min+g[k][j];
                prev_v[j] = k;
            }
        }
    }
}           

大餐來了，迪傑斯特拉算法來了！

該函數傳入的參數是圖和源點。

我們使用一個數組來标記是否源點到該點已經找出了最短路徑。

再将final、short_path、prev_v初始化，将v0的所有邊加入short_path。

因為源點到源點的最短距離已經确定了是0，是以我們将final[v0]标記為1，short_path[v0]标記為0。

然後接下來的第一個循環表示一共需要找MAXVEX-1條最短路徑，然後從源點到剩餘未被标記的頂點中尋找最短的一條路徑。然後将找到的下一個點标記，表示源點到該點的路徑已經找到。

然後看一看源點到其它各頂點（尚未确定最短路徑的頂點）的最短路徑中，如果途經頂點k的路徑長度比原路徑更短,就更新。并設定k為j的前置節點。

3. 輸出最短路徑

void show_shortest_path( int source ,int end) {
    int que[10];
    int tot = 1;
    printf("source到%d的最短路徑: ",end);
    que[tot] = end;
    tot++;

    int i = prev_v[end];
    while(i != source) {
        que[tot] = i;
        tot++;
        i = prev_v[i];
    }
    que[tot] = source;
    for(int i=tot;i>=1;i--){
        if(i!=1){
            printf("%d->",que[i]);
        }else{
            printf("%d",que[i]);
        }
        
    }
    printf("\n");
}           

就是建一個數組當作隊列，然後将每次找到的節點放到隊列中，然後順序周遊。