圖論——最短路——Dijkstra算法

對圖論有一定了解的人，一定知道最短路。

最短路算法一共有4中，嚴格來說是3種，應為最後一個是第3個的優化。

他們分别是：

Floyd、Dijkstra、Bellman-Ford和SPFA算法

Floyd是最暴力的思想，這裡就不在闡述。

今天，我們來講Dijkstra算法，中文名迪傑斯特拉。

Dijkstra是單源最短路，也就是計算從一點出發，到各個點的距離。

這是一個類似貪心的算法，是否流程如下：

1.初始化dist [ v0 ] = 0;(v0是源點)，其餘dist為INF（正無窮，通常用0x3f3f3f3f表示）

2.找出未标記的、dist [ x ] 的最小 x ，标記 x；

3.掃描節點x的所有 出邊 （x，y，z）表示x到y有權值為z的邊。，若dist [ y ] > dist [ x ] + z,則使用 dist [ x ] + z 更新 dist [ y ]；

4.重複2~3，直到所有點都被标記。

dist [ x ] 就是 v0 到 x 的最短路徑。

代碼實作：

1 int a[3010][3010]/*圖*/,d[3010],n,m;
 2 bool v[3010];//是否被通路
 3 void dijkstra(int v0)//源點
 4 {
 5     memset(d,0x3f3f3f3f,sizeof(d));//距離
 6     memset(v,0,sizeof(v));//初始化都未通路
 7     d[v0]=0;
 8     for(int i=1;i<n;i++)//重複n-1次 
 9     {
10         int x=0;
11         //找到未标記的dist最小的節點
12         for(int j=1;j<=n;j++)
13             if(!v[j]&&(x==0||d[j]<d[x]))//j為通路或dist[j]<dist[x]; 
14                 x=j;
15         v[x]=1;
16         //用x更新其他點 
17         for(int y=1;y<=n;y++)
18             d[y]=min(d[y],d[x]+a[x][y]/*x到y的邊權值*/); 
19     }
20 }      

這就是模闆of Dijkstra，很好了解，大家要是有不了解的，也可以查相關資料，去了解更多的知識。