相關文獻：
數據結構與算法(一)：基礎理論
數據結構與算法(二)：線性表的實現
數據結構與算法(三)：線性表算法設計練習
數據結構與算法(四)：斐波那契數列
數據結構與算法(五)：LRU
數據結構與算法(六)：棧
數據結構與算法(七)：棧/隊列的算法解題思想
數據結構與算法(八)：隊列
數據結構與算法(九)：樹形結構/二叉樹/線索化二叉樹
數據結構與算法(十)：哈夫曼樹
數據結構與算法(十一)：圖形結構
數據結構與算法(十二)：圖的應用-最小生成樹-Prim/Kruskal
數據結構與算法(十三)：圖的應用-最短路徑-Dijkstra/Floyd
數據結構與算法(十四)：圖的應用-拓撲排序/關鍵路徑
數據結構與算法(十五)：查找算法-順序查找/二分查找/二叉搜索樹/平衡二叉樹/散列表查找
數據結構與算法(十六)：排序算法

一、最短路徑

當你從一個城市去到另一個城市，可以選擇中間跨越不同的地方，選擇不一樣的路徑，最終到達終點。

最短路徑就是從起點到達終點怎么走是最短的，但是會面臨兩種情況：1.帶權值的網圖；2.不帶權值的連通圖。

• 1.帶權值的網圖：從起點到終點所累積的權值總和最?。嘀悼衫斫獬陕烦蹋?；
• 2.不帶權值的連通圖：從起點到終點的邊數總和最小。

舉例網圖：

帶權值的網圖

要從V0出發(fā)到V8

最短路徑: V0 — V1 — V2 — V4 — V3 —V6 —V7 — V8
最短路徑權值和: 1 + 3 + 1 + 2 +3 + 2 + 4 = 16

二、最短路徑 - 迪迦斯特(Dijkstra)算法

帶權值的網圖

用鄰接矩陣存儲網圖

鄰接矩陣存儲網圖

1.算法分析

定義三個數組去記錄

• 從0開始：

//V0到V0是沒有路徑的.
final[v0] = 1; 
//V0到V0的路徑為0
(*D)[v0] = 0;
//V0到V0是沒有路徑的.所以-1;
(*P)[v0] = -1;

final數組：表示V0 到某個頂點 Vw 是否已經求得了最短路徑的標記；
如果V0 到 Vw 已經有結果，則final[w] = 1。（避免往回走的情況）

D數組：表示V0 到某些頂點的路徑，∞表示暫時還不能直接到達；
此時的數據是此時是V0所能到達頂點。

現在D數組是V0到其它頂點的直接路徑，但是我們代碼回去修改數組的數據，變成間接路徑。

p數組：存儲當前頂點的前驅頂點的下標。-1表示V0出發(fā)還沒有前驅。

• 第1次執(zhí)?：看找到V1是怎么記錄的

V0->V1的權值 = 1
V0->V2的權值 = 5

在D數組中V1的權值更小(1<5，0不考慮是因為final標記過為1)，所以min=1 (min記錄上一次邊權值)。

final數組:
V0->V1存在最短路徑 final[1] = 1 標記好防止往回找。

此時V1能直接到的地方：V0、V2、V3、V4，由于V0在final數組中已經標記過了不能回流，所以此時只剩下V2、V3、V4

D數組：
V0->V1->V2的權值 = min+3 = 4 < 5，此刻D[2] = 4代替掉原本的5；
V0->V1->V3的權值 = min+7 = 8 < ∞，此刻D[3] = 8代替掉原本的∞；
V0->V1->V4的權值 = min+5 = 6 < ∞，此刻D[4] = 6代替掉原本的∞。

p數組：

p數組記錄V2、V3、V4的前驅頂點是V1。

• 第2次執(zhí)?：看找到V2是怎么記錄的

看D數組中的數據：
V0->V1->V2的權值 = 4
V0->V1->V3的權值 = 8
V0->V1->V4的權值 = 6

在D數組中V2的權值更小(4<6<8)，所以min=4 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2存在最短路徑 final[2] = 1 標記好防止往回找。

此時V2能直接到的地方：V0、V1、V4、V5，由于V0/V1在final數組中已經標記過了不能回流，所以此時只剩下V4、V5。

D數組：
V0->V1->V2->V4的權值 = min+1 = 5 < 6，此刻D[4] = 5代替掉原本的6；
V0->V1->V2->V5的權值 = min+7 = 11 < ∞，此刻D[5] = 11代替掉原本的∞；

p數組：

p數組記錄V4、V5的前驅頂點是V2。

• 第3次執(zhí)?：看找到V4是怎么記錄的

看D數組中的數據：
由于final標記了V0、V1、V2存在最短路徑，無需看在D數組中的V0、V1、V2：
V0->V1->V3的權值 = 8
V0->V1->V2->V4的權值 = 5
V0->V1->V2->V5的權值 = 11

在D數組中V4的權值更小(5<8<11)，所以min=5 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2->V4存在最短路徑 final[4] = 1 標記好防止往回找。

此時V2能直接到的地方：V1、V2、V3、V5、V6、V7，由于V1/V2在final數組中已經標記過了不能回流，所以此時只剩下V3、V5、V6、V7。

D數組：
V0->V1->V2->V4->V3的權值 = min+2 = 7 < 8，此刻D[3] = 7代替掉原本的8；
V0->V1->V2->V4->V5的權值 = min+3 = 8 < 11，此刻D[5] = 8代替掉原本的11；
V0->V1->V2->V4->V6的權值 = min+6 = 11 < ∞，此刻D[6] = 11代替掉原本的∞；
V0->V1->V2->V4->V7的權值 = min+9 = 14 < ∞，此刻D[7] = 14代替掉原本的∞。

p數組：

p數組記錄V3、V5、V6、V7的前驅頂點是V4。

• 第4次執(zhí)?：看找到V3是怎么記錄的

看D數組中的數據：
由于final標記了V0、V1、V2、V4存在最短路徑，無需看在D數組中的V0、V1、V2、V4：
V0->V1->V2->V4->V3的權值 = 7
V0->V1->V2->V4->V5的權值 = 8
V0->V1->V2->V4->V6的權值 = 11
V0->V1->V2->V4->V7的權值 = 14

在D數組中V4的權值更小(7<8<11<14)，所以min=7 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2->V4->V3存在最短路徑 final[3] = 1 標記好防止往回找。

此時V3能直接到的地方：V1、V4、V6，由于V1/V4在final數組中已經標記過了不能回流，所以此時只剩下V6。

D數組：
V0->V1->V2->V4->V3->V6的權值 = min+3 = 10 <11，此刻D[6] = 10代替掉原本的11。

p數組：

p數組記錄V6的前驅頂點是V3。

• 第5次執(zhí)?：看找到V6后，為啥去找V5->V7

看D數組中的數據：
由于final標記了V0、V1、V3、V2、V4存在最短路徑，無需看在D數組中的V0、V1、V3、V2、V4：
V0->V1->V2->V4->V5的權值 = 8
V0->V1->V2->V4->V3->V6的權值 = 10
V0->V1->V2->V4->V7的權值 = 14

在D數組中V4的權值更小(8<10<14)，所以min=8 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2->V4->V5存在最短路徑 final[5] = 1 標記好防止往回找。

此時V4能直接到的地方：只剩下V5、V6、V7（因為其它位已被final標記）。

D數組：
V0->V1->V2->V4->V5的權值 = min+3 = 11 > 8，此刻D[5]依舊為8；
V0->V1->V2->V4->V6的權值 = min+6 = 14 <10，此刻D[6]依舊為10；
V0->V1->V2->V4->V7的權值 = min+9 = 17 <14，此刻D[7] 依舊為14；
V0->V1->V2->V4->V5->V7的權值 = min+5 = 13 < 14,此刻D[7] = 13代替掉原本的14。

p數組：

p數組記錄V7的前驅頂點是V5。

• 第6次執(zhí)?：權衡V5/V6，決定V6->V7

看D數組中的數據：
由于final標記了V0、V1、V2、V3、V4、V5存在最短路徑，無需看在D數組中的V0、V1、V2、V3、V4、V5：
V0->V1->V2->V4->V3->V6的權值 = 10
V0->V1->V2->V4->V5->V7的權值 = 13

在D數組中V6的權值更小(0<13)，所以min=10 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2->V4->V3->V6存在最短路徑 final[6] = 1 標記好防止往回找。

此時V6能直接到的地方：只剩下V7、V8（因為V3/V4已被final標記）。

D數組：
V0->V1->V2->V4->V3->V6->V7的權值 = min+2 = 12 < 13，此刻D[7] = 12代替掉原本的13;
V0->V1->V2->V4->V6->V8的權值 = min+7 = 17 < ∞，此刻D[8] = 17代替掉原本的∞。

p數組：

p數組記錄V7、V8的前驅頂點是V6。

• 第7次執(zhí)?：權衡V6/V7，決定V7->V8

看D數組中的數據：
由于final標記了V0、V1、V2、V3、V4、V5、V6存在最短路徑，無需看在D數組中的V0、V1、V2、V3、V4、V5、V6：
V0->V1->V2->V4->V3->V6->V7的權值 = 12
V0->V1->V2->V4->V3->V6->V8的權值 = 17

在D數組中V6的權值更小(12<17)，所以min=12 (min記錄上一次邊權值)。

final數組:
在V0->V1->V2->V4->V3->V6->V7存在最短路徑 final[7] = 1 標記好防止往回找。

此時V7能直接到的地方：只剩下V8。

D數組：
V0->V1->V2->V4->V3->V6->V7->V8的權值 = min+4 = 16 < 17，此刻D[7] = 16代替掉原本的17。

p數組：

p數組記錄V8的前驅頂點是V7。

• 第8次執(zhí)?：確定V8的路徑

由于此時final數組里只有V8沒有被標記，所以min=16 == 16

final數組:
在V0->V1->V2->V4->V3->V6->V7->V8存在最短路徑 final[8] = 1。

D數組、p數組都不變

此時D數組存儲的就是V0到每一個頂點的最短路徑的權值之和；
此時p數組存儲的就是V0出發(fā)，每一個頂點的前驅。

2.算法實現

• 通過鄰接矩陣創(chuàng)建圖

#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/*用于存儲最短路徑下標的數組*/
typedef int Patharc[MAXVEX];
/*用于存儲到各點最短路徑權值的和*/
typedef int ShortPathTable[MAXVEX];

/*10.1 創(chuàng)建鄰近矩陣*/
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

• Dijkstra算法實現

/*10.2 求得網圖中2點間最短路徑
 Dijkstra 算法
 G: 網圖;
 v0: V0開始的頂點;
 p[v]: 前驅頂點下標;
 D[v]: 表示從V0到V的最短路徑長度和;
 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
    int v,w,k,min;
    k = 0;
    /*final[w] = 1 表示求得頂點V0~Vw的最短路徑*/
    int final[MAXVEX];
    
    /*1.初始化數據*/
    for(v=0; v<G.numVertexes; v++)
    {
        //全部頂點初始化為未知最短路徑狀態(tài)0
        final[v] = 0;
        //將與V0 點有連線的頂點最短路徑值;
        (*D)[v] = G.arc[v0][v];
        //初始化路徑數組p = 0;
        (*P)[v] = 0;
    }
    
    //V0到V0的路徑為0
    (*D)[v0] = 0;
    //V0到V0 是沒有路徑的.
    final[v0] = 1;
    //v0到V0是沒有路徑的
    (*P)[v0] = -1;
    
  
    
    //2. 開始主循環(huán),每次求得V0到某個頂點的最短路徑
    for(v=1; v<G.numVertexes; v++)
    {
        
        //當前所知距離V0頂點最近的距離
        min=INFINITYC;
        /*3.尋找離V0最近的頂點*/
        for(w=0; w<G.numVertexes; w++)
        {
            if(!final[w] && (*D)[w]<min)
            {
                k=w;
                //w頂點距離V0頂點更近
                min = (*D)[w];
            }
        }
        
        //將目前找到最近的頂點置為1;
        final[k] = 1;
        
        /*4.把剛剛找到v0到v1最短路徑的基礎上,對于v1 與 其他頂點的邊進行計算,得到v0與它們的當前最短距離;*/
        for(w=0; w<G.numVertexes; w++)
        {
            //如果經過v頂點的路徑比現在這條路徑長度短,則更新
            if(!final[w] && (min + G.arc[k][w]<(*D)[w]))
            {
                //找到更短路徑, 則修改D[W],P[W]
                //修改當前路徑的長度
                (*D)[w] = min + G.arc[k][w];
                (*P)[w]=k;
            }
        }
    }
}

int main(void)
{
    printf("最短路徑-Dijkstra算法\n");
    int i,j,v0;
    MGraph G;
    Patharc P;
    ShortPathTable D;
    v0=0;
    
    CreateMGraph(&G);
    
    ShortestPath_Dijkstra(G, v0, &P, &D);
    
    printf("最短路徑路線:\n");
    for(i=1;i<G.numVertexes;++i)
    {
        printf("v%d -> v%d : ",v0,i);
        j=i;
        while(P[j]!=-1)
        {
            printf("%d ",P[j]);
            j=P[j];
        }
        printf("\n");
    }
    
    printf("\n最短路徑權值和\n");
    for(i=1;i<G.numVertexes;++i)
        printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);
    
    printf("\n");
    return 0;
}

三、最短路徑 - 弗洛伊德(Floyd)算法

1.簡化推演公式

求 V1->V2 最短路徑?

有 V1->V2 = 5 或者 V1->V0->V2 = 3 兩種路徑；
該圖的鄰接矩陣就可以有下面這樣的演變：

D數組存儲 最短路徑權值

P數組存儲 前驅節(jié)點

于是推演出該公式：

2.算法執(zhí)行過程分析

帶權值的網圖

得到初始化的兩個臨街矩陣 D和P：

/* 1. 初始化D與P 矩陣*/
for(v=0; v<G.numVertexes; ++v) {
  for(w=0; w<G.numVertexes; ++w) {
    /* D[v][w]值即為對應點間的權值 */
    (*D)[v][w]=G.arc[v][w];
    /* 初始化P P[v][w] = w*/
    (*P)[v][w]=w;
   }
 }

初始化兩個鄰接矩陣 D和P

最短路徑的遍歷：

//2.K表示經過的中轉頂點
for(k=0; k<G.numVertexes; ++k)  {
  for(v=0; v<G.numVertexes; ++v) {
    for(w=0; w<G.numVertexes; ++w) {
      /*如果經過下標為k頂點路徑?原兩點間路徑更短 */
      if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w]) {
        /* 將當前兩點間權值設為更?的?個 */
        (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
        /* 路徑設置為經過下標為k的頂點 */
        (*P)[v][w]=(*P)[v][k];
      }
    }
  }
}

根據公式去推導

• 第1次執(zhí)?：
  當 K = 0 時, 也就是所有頂點都經過V0中轉, 計算是否有最短路徑的變化。所以k=0時，D和P沒有發(fā)?任何變換。

• 第2次執(zhí)?：
  當 K = 1 時, 也就是所有頂點都經過V1 中轉

D矩陣的變化

P矩陣的變化

（下面就不畫圖了，直接給執(zhí)行過程，并不完全，只是給個套上公式后的推導）

這里只分析到K=1的情況，下面還有好多好多....
該算法時間復雜度是 83。

最終得到的D和P的存儲數據如下：

最終數據D和P

D矩陣存放了每一個頂點到任意一個頂點的最短路徑，比如V2->V8是12；
以V2->V8來看，P矩陣應該這樣看：
V2->V8 經歷過V4 （P[2][8]）
V2->V4->V8 經歷過V3 （P[4][8]）
V2->V4->V3->V8 經歷過V6 （P[3][8]）
V2->V4->V3->V6->V8 經歷過V7 （P[6][8]）
V2->V4->V3->V6->V7->V8 經歷過V8 （P[7][8]）
V2->V4->V3->V6->V7->V8才是最終的路徑 （P[8][8]）

3. 算法實現

• 初始化圖

#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函數的類型,其值是函數結果狀態(tài)代碼，如OK等 */

typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

/* 11.1 構成鄰近矩陣 */
void CreateMGraph(MGraph *G)
{
    int i, j;
    
    /* printf("請輸入邊數和頂點數:"); */
    G->numEdges=16;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        G->vexs[i]=i;
    }
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=1;
    G->arc[0][2]=5;
    G->arc[1][2]=3;
    G->arc[1][3]=7;
    G->arc[1][4]=5;
    
    G->arc[2][4]=1;
    G->arc[2][5]=7;
    G->arc[3][4]=2;
    G->arc[3][6]=3;
    G->arc[4][5]=3;
    
    G->arc[4][6]=6;
    G->arc[4][7]=9;
    G->arc[5][7]=5;
    G->arc[6][7]=2;
    G->arc[6][8]=7;
    
    G->arc[7][8]=4;
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

• Floyd算法

/* 11. 2
 Floyd算法，求網圖G中各頂點v到其余頂點w的最短路徑P[v][w]及帶權長度D[v][w]。
 Patharc 和 ShortPathTable 都是二維數組;
 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
    int v,w,k;
    
    /* 1. 初始化D與P 矩陣*/
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            /* D[v][w]值即為對應點間的權值 */
            (*D)[v][w]=G.arc[v][w];
             /* 初始化P P[v][w] = w*/
            (*P)[v][w]=w;
        }
    }
    
    //2.K表示經過的中轉頂點
    for(k=0; k<G.numVertexes; ++k)
    {
        for(v=0; v<G.numVertexes; ++v)
        {
            for(w=0; w<G.numVertexes; ++w)
            {
                /*如果經過下標為k頂點路徑比原兩點間路徑更短 */
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
                {
                    /* 將當前兩點間權值設為更小的一個 */
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                    /* 路徑設置為經過下標為k的頂點 */
                    (*P)[v][w]=(*P)[v][k];
                }
            }
        }
    }
}

int main(void)
{
    printf("Hello,最短路徑弗洛伊德Floyd算法");
    int v,w,k;
    MGraph G;
    
    Patharc P;
    ShortPathTable D; /* 求某點到其余各點的最短路徑 */
    
    CreateMGraph(&G);
    
    ShortestPath_Floyd(G,&P,&D);
    
    //打印所有可能的頂點之間的最短路徑以及路線值
    printf("各頂點間最短路徑如下:\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=v+1; w<G.numVertexes; w++)
        {
            printf("v%d-v%d weight: %d ",v,w,D[v][w]);
            //獲得第一個路徑頂點下標
            k=P[v][w];
            //打印源點
            printf(" path: %d",v);
            //如果路徑頂點下標不是終點
            while(k!=w)
            {
                //打印路徑頂點
                printf(" -> %d",k);
                //獲得下一個路徑頂點下標
                k=P[k][w];
            }
            //打印終點
            printf(" -> %d\n",w);
        }
        printf("\n");
    }
    
    //打印最終變換后的最短路徑D數組
    printf("最短路徑D數組\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d\t",D[v][w]);
        }
        printf("\n");
    }
    //打印最終變換后的最短路徑P數組
    printf("最短路徑P數組\n");
    for(v=0; v<G.numVertexes; ++v)
    {
        for(w=0; w<G.numVertexes; ++w)
        {
            printf("%d ",P[v][w]);
        }
        printf("\n");
    }
    
    return 0;
}