1. 何為最短路徑

最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑，大致可以分為如下幾種問題，可無論如何分類問題，其本質(zhì)思想還是不變的，即，求兩點(diǎn)間的最短距離。

a) 確定起點(diǎn)的最短路徑問題 - 即已知起始結(jié)點(diǎn)，求最短路徑的問題。

b) 確定終點(diǎn)的最短路徑問題 - 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。

c) 確定起點(diǎn)終點(diǎn)的最短路徑問題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。

d) 全局最短路徑問題 - 求圖中所有的最短路徑。

2. 迪杰斯特拉算法介紹

如上圖，迪杰斯特拉算法的核心思路是：

1) 指定一個節(jié)點(diǎn)，例如我們要計(jì)算 'A' 到其他節(jié)點(diǎn)的最短路徑

2) 引入兩個集合（S、U），S集合包含已求出的最短路徑的點(diǎn)（以及相應(yīng)的最短長度），U集合包含未求出最短路徑的點(diǎn)（以及A到該點(diǎn)的路徑，注意 如上圖所示，A->C由于沒有直接相連 初始時為∞）

3) 初始化兩個集合，S集合初始時 只有當(dāng)前要計(jì)算的節(jié)點(diǎn)，A->A = 0，

4) U集合初始時為 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞

5) 從U集合中找出路徑最短的點(diǎn)，加入S集合，例如 A->D = 2

6) 更新U集合路徑，if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 則更新U

7) 循環(huán)執(zhí)行 4、5 兩步驟，直至遍歷結(jié)束，得到A 到其他節(jié)點(diǎn)的最短路徑

3. 樣例代碼

代碼僅供參考

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
 
#define INFINITY 65535//無邊時的權(quán)值
#define MAX_VERTEX_NUM 10//最大頂點(diǎn)數(shù)
 
typedef struct MGraph {
    string vexs[10];//頂點(diǎn)信息
    int arcs[10][10];//鄰接矩陣
    int vexnum, arcnum;//頂點(diǎn)數(shù)和邊數(shù)
} MGraph;
 
int LocateVex(MGraph G, string u) { //返回頂點(diǎn)u在圖中的位置
    for(int i=0; i<G.vexnum; i++)
        if(G.vexs[i]==u)
            return i;
    return -1;
}
 
void CreateDN(MGraph &G) { //構(gòu)造有向網(wǎng)
    string v1, v2;
    int w;
    int i, j, k;
    cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)：";
    cin>>G.vexnum>>G.arcnum;
 
    cout<<"請輸入頂點(diǎn)：";
    for(i=0; i<G.vexnum; i++)
        cin>>G.vexs[i];
 
    for(i=0; i<G.vexnum; i++)
        for(j=0; j<G.vexnum; j++)
            G.arcs[i][j]=INFINITY;
 
    cout<<"請輸入邊和權(quán)值："<<endl;
    for(k=0; k<G.arcnum; k++) {
        cin>>v1>>v2>>w;
        i=LocateVex(G, v1);
        j=LocateVex(G, v2);
        G.arcs[i][j]=w;
    }
}
 
//迪杰斯特拉算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑p[v]及帶權(quán)長度D[v]
//p[][]=-1表示沒有路徑，p[v][i]存的是從v0到v當(dāng)前求得的最短路徑經(jīng)過的第i+1個頂點(diǎn)(這是打印最短路徑的關(guān)鍵)，則v0到v的最短路徑即為p[v][0]到p[v][j]直到p[v][j]=-1,路徑打印完畢。
//final[v]為true當(dāng)且僅當(dāng)v∈S,即已經(jīng)求得從v0到v的最短路徑。
void ShortestPath_DIJ(MGraph G, int v0, int p[][MAX_VERTEX_NUM], int D[]) {
    int v, w, i, j, min;
    bool final[10];
 
    for(v=0; v<G.vexnum; v++) {
        final[v]=false;//設(shè)初值
        D[v]=G.arcs[v0][v];//D[]存放v0到v得最短距離，初值為v0到v的直接距離
        for(w=0; w<G.vexnum; w++)
            p[v][w]=-1;//設(shè)p[][]初值為-1，即沒有路徑
        if(D[v]<INFINITY) { //v0到v有直接路徑
            p[v][0]=v0;//v0到v最短路徑經(jīng)過的第一個頂點(diǎn)
            p[v][1]=v;//v0到v最短路徑經(jīng)過的第二個頂點(diǎn)
        }
    }
 
    D[v0]=0;//v0到v0距離為0
    final[v0]=true;//v0頂點(diǎn)并入S集
 
    for(i=1; i<G.vexnum; i++) { //其余G.vexnum-1個頂點(diǎn)
        //開始主循環(huán)，每次求得v0到某個頂點(diǎn)v的最短路徑，并將v并入S集，然后更新p和D
        min=INFINITY;
        for(w=0; w<G.vexnum; w++)//對所有頂點(diǎn)檢查
            if(!final[w] && D[w]<min) { //在S集之外(即final[]=false)的頂點(diǎn)中找離v0最近的頂點(diǎn)，將其賦給v,距離賦給min
                v=w;
                min=D[w];
            }
        final[v]=true;//v并入S集
        for(w=0; w<G.vexnum; w++) { //根據(jù)新并入的頂點(diǎn)，更新不在S集的頂點(diǎn)到v0的距離和路徑數(shù)組
            if(!final[w] && min<INFINITY && G.arcs[v][w]<INFINITY && (min+G.arcs[v][w]<D[w])) {
                //w不屬于S集且v0->v->w的距離<目前v0->w的距離
                D[w]=min+G.arcs[v][w];//更新D[w]
                for(j=0; j<G.vexnum; j++) { //修改p[w]，v0到w經(jīng)過的頂點(diǎn)包括v0到v經(jīng)過的所有頂點(diǎn)再加上頂點(diǎn)w
                    p[w][j]=p[v][j];
                    if(p[w][j]==-1) { //在p[w][]第一個等于-1的地方加上頂點(diǎn)w
                        p[w][j]=w;
                        break;
                    }
                }
 
            }
        }
    }
}
 
int main() {
    int i, j;
    MGraph g;
    CreateDN(g);
    int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//最短路徑數(shù)組p
    int D[MAX_VERTEX_NUM];//最短距離數(shù)組D
    ShortestPath_DIJ(g, 0, p, D);
 
    cout<<"最短路徑數(shù)組p[i][j]如下："<<endl;
    for(i=0; i<g.vexnum; i++) {
        for(j=0; j<g.vexnum; j++)
            cout<<setw(3)<<p[i][j]<<" ";
        cout<<endl;
    }
 
    cout<<g.vexs[0]<<"到各頂點(diǎn)的最短路徑及長度為："<<endl;
    for(i=0; i<g.vexnum; i++) {
        if(i!=0 && D[i]!=INFINITY) {
            cout<<g.vexs[0]<<"-"<<g.vexs[i]<<"的最短路徑長度為:"<<D[i];
            cout<<"  最短路徑為：";
            for(j=0; j<g.vexnum; j++) {
                if(p[i][j]>-1)
                    cout<<g.vexs[p[i][j]]<<" ";
            }
            cout<<endl;
        } else if(D[i]==INFINITY)
            cout<<g.vexs[0]<<"-"<<g.vexs[i]<<":"<<"不可達(dá)"<<endl;
    }
    return 0;
}