迪克斯切算法編程

迪克斯切

迪杰斯特拉算法用于求解一個有向圖（也可以是無向圖，無向圖是有向圖的一種特例）的一個點（稱之為原點）到其余各點（稱之為周邊點）的最短路徑問題。算法構(gòu)思很是巧妙（我這么認(rèn)為），簡直達(dá)到了“無心插柳柳成蔭”的境界。算法本身并不是按照我們的思維習(xí)慣——求解從原點到第一個點的最短路徑，再到第二個點的最短路徑，直至最后求解完成到第n個點的最短路徑，而是求解從原點出發(fā)的各有向路徑的從小到大的排列（如果這個有向圖中有環(huán)1-2-3-1算法豈不是永無終結(jié)之日了？？?。。?，但是算法最終確實得到了從原點到圖中其余各點的最短路徑，可以說這是個副產(chǎn)品，對于算法的終結(jié)條件也應(yīng)該以求得了原點到圖中其余各點的最短路徑為宜。清楚了算法的這種巧妙構(gòu)思后，理解算法本身就不是難題了。

算法把一個圖（G）中的點劃分成了若干部分：

1）：原點（v）；

2）：所有周邊點（C）；

另外有一個輔助集合S，從v到S中的點的最短路徑已經(jīng)求得。S的最初狀態(tài)是空集。

這樣就可以進(jìn)一步劃分圖（G）：

1）：原點（v）；

2）：已求出v至其最短路徑的周邊點（S）；

3）：尚未求出v至其最短路徑的周邊點（Other=C-S）；

算法的主體思想：

A、找到v——Other所有路徑中的的最短路徑vd=v——d（Other的一個元素）；

B、找到v——S——Other所有路徑中的的最短路徑vi=v——i（Other的一個元素）；

C、比較vd和vi如果vd《=vi則將d加入S且從Other中刪除，否則將i加入S且從Other中刪除。

重復(fù)以上步驟直至Other為空集。

我們求得的最短路徑是升序排列的，那為什么下一條最短路徑就存在于v——