最短路徑

在網(wǎng)圖和非網(wǎng)圖中，最短路徑的含義是不同的。對于非網(wǎng)圖，由于其邊上沒有權值，所謂的最短路徑，其實就是指兩頂點之間經(jīng)過的邊數(shù)最少的路徑。而對于網(wǎng)圖，最短路徑，是指兩頂點之間經(jīng)過的邊上權值之和最少的路徑。

和最小生成樹的區(qū)別：

最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。

最短路徑是從一點出發(fā)，到達目的地的路徑最小。

Prim 和 Dijkstra 代碼非常相似，都是這樣一個大體步驟：初始化，找最小值，更新權值數(shù)組。注意對比他們的代碼。

迪杰斯特拉算法(Dijkstra)

按路徑長度遞增的次序產生最短路徑。

一步一步求出他們之間頂點的最短路徑，過程中都是基于已經(jīng)求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得到你要的結果。

#include "鄰接矩陣.h"
#define MAXVEX 9
#define INF 65535
typedef int Patharc[MAXVEX];
typedef int ShortPathTable[MAXVEX];
void
Dijkstra(MGraph G, int begin, Patharc *P, ShortPathTable *D)
{
    /*
    ShortPathTable數(shù)組 表示 begin 到 某頂點的"最短路徑和"
    Patharc數(shù)組 比如P[v] = w，表示 v的前驅為w
    */
    int v, w, k, min;/*k用來存放最小值min對應的頂點下標*/
    int final[MAXVEX]; /*存放begin 到 某頂點 是否已經(jīng)求得最短路徑，如果begin到v2已經(jīng)求得，final[2] = 1*/
    for(v = 0; v < G.numVertexes; v++)
    {
        final[v] = 0; /*所有頂點都未求得最短路徑*/
        (*D)[v] = G.arc[begin][v];
        (*P)[v] = -1;/*這里書上是0，是錯誤的，更正為-1后，每當一個結點的前驅為-1，即等同于它的前驅為begin
        如初始化第一次還是計算從begin到各頂點的權值。如果D[v] = 3;P[v] = -1; 就表示從begin到v的最短路徑和為3； 
        */
    }
    (*D)[begin] = 0; /*起始點到起始點的路徑為0，如果對角線用INF表示這行代碼是必須的，如果用0表示對角線，這行代碼多余*/
    final[begin] = 1;/*起始點到起始點不需要求路徑*/

    /*初始化結束 開始循環(huán)生成最短路徑*/
    for(v = 1; v < G.numVertexes; v++)
    {
        /*這里為什么循環(huán)是從1開始的，因為頂點begin已經(jīng)再=在最短路徑中，不需要再求*/
        /*尋找D數(shù)組中沒有被納入Final數(shù)組的部分的最小值*/
        min = INF;
        for(w = 0; w < G.numVertexes; w++)
        {
            if(!final[w] && (*D)[w] < min)
            {
                k = w;
                min = (*D)[w];
            }
        }
        final[k] = 1;
        /*找到最小值，相應下標頂點納入final數(shù)組，=1表面該頂點已經(jīng)在最小路徑中。*/
        /*更新從begin到各未被納入頂點的值，如果小于先前的最小路徑和，就更新，并把頂點的前驅在P數(shù)組中置為之前求得的k，這里有這樣一個對應關系*/
        for(w = 0; w < G.numVertexes; w++)
        {
            if(!final[w] && (min+G.arc[k][w] < (*D)[w]))
            {
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}