Dijkstra算法思想
Dijkstra算法的思想是:設G=(V，E)是壹個加權有向圖(無向可以轉化為雙向有向圖)，將圖中的頂點集V分成兩組。第壹組是已經找到最短路徑的頂點集(用S表示，初始S中只有壹個源點，以後每找到壹條最短路徑，就加到集合S中，直到所有頂點都加到S中，算法結束。在拼接過程中，始終保持源點V到S中每個頂點的最短路徑長度不大於源點V到U中任意頂點的最短路徑長度，另外，每個頂點對應壹個距離，S中頂點的距離就是V到這個頂點的最短路徑長度，U中頂點的距離就是V到這個頂點的當前最短路徑長度，只包括S中的頂點作為中間頂點。
Dijkstra算法的具體步驟
(1)最初，s只包含源點，即s = {v}，v的距離dist[v]為0。U包含除V以外的其他頂點，U中頂點之間的距離dis[u]，是邊的權(如果V和U有邊)或∞(如果U不是V的邊鄰點，則沒有邊< V，u & gt)。
(2)從U中選擇壹個距離v(dist[k])最小的頂點K，將K加到S上(所選距離為V到K的最短路徑長度)。
(3)以K為新考慮的中間點，修改U中每個頂點的距離；如果從源點V到頂點u(u∈ U)(經過頂點K)的距離比原來的距離(不經過頂點K)短，則修改頂點U的距離值，並將修改後的距離值的頂點K的距離加上邊權重(即如果dist [k]+w [k，u]
(4)重復步驟(2)和(3)，直到所有頂點都包含在S中(循環n-1次)。
╝①
Dijkstra算法的實現
╔
直接實現
最簡單的方法是在每個循環中找到距離最短的點，然後用任何方法更新它的相鄰邊。時間復雜度明顯是O(n？)
對於空間復雜度:如果只需要求距離，只需要將距離保存在n的額外空間中即可(如果距離小於當前距離，可以進行數字比較或者對相同距離進行特殊處理)。如果需要路徑，則需要另壹個V空間來保存前壹個節點，總共* * *需要2n空間。
╝②
╔
Cpp代碼
/*********************************
*最短路徑- Dijkstra算法實現
*HDU:2544人
*博客:www.cnblogs.com/newwy
*作者:王勇
**********************************/
# include & ltiostream & gt
#定義最大100
#定義INF 100000000
使用命名空間std
int dijkstra (int mat[][MAX]，int n，int s，int f)
{
int dis[MAX]；
int mark[MAX]；//記錄選中的節點。
int i，j，k = 0；
for(I = 0；我& ltn；I++)//初始化所有節點，不選擇每個節點。
mark[I]= 0；
for(I = 0；我& ltn；I++)//記錄每個節點到起始節點的權重作為當前距離。
{
dis[I]= mat[s][I]；
//path[I]= s；
}
mark[s]= 1；//選擇//開始節點
//path[s]= 0；
dis[s]= 0；//將起始節點的距離設置為0。
int min//設置最短距離。
for(I = 1；我& ltn；i++)
{
min = INF
for(j = 0；j & ltn；j++)
{
if(mark[j]= = 0 & amp；& ampdis[j]& lt；Min)//在未選擇的節點中，選擇距離最短的節點。
{
min = dis[j]；
k = j；
}
}
mark[k]= 1；//標記為選中
for(j = 0；j & ltn；j++)
{
if(mark[j]= = 0 & amp；& amp(dis[j]& gt；(dis[k]+mat[k][j])//修改剩余節點的最短距離。
{
dis[j]= dis[k]+mat[k][j]；
}
}
}
return dis[f]；
}
int mat[MAX][MAX]；
int main()
{
int n，m；
while(scanf("%d %d "，& ampn & amp；m))
{
int a，b，dis
如果(n == 0 || m == 0)
打破；
int i，j；
for(I = 0；我& ltn；i++)
for(j = 0；j & ltn；j++)
mat[I][j]= INF；
for(I = 0；我& ltm；i++)
{
scanf("%d %d %d "，& amp壹，& ampb & amp；dis)；
- a，-b；
if(dis & lt；mat[a][b]| | dis & lt；mat[b][a])
mat[a][b]= mat[b]= dis；
}
int ans = dijkstra(mat，n，0，n-1)；
printf("%d\n "，ans)；
}
}
╝⑤
╔
二進制堆實現
使用二進制堆保存未擴展點的距離並保持其最小值，在訪問每條邊時更新，時間復雜度可變為O((V+E)logV)。
當邊數遠小於點數的平方時，該算法具有相對較好的效果。但當E=O(V2)時(有時說明邊數不限)，用二進制堆優化會慢壹些。因為此時的復雜度是O(V+V*2logV)，比O(n？)復雜。
另外，要用鄰接表保存邊，使擴展邊的總復雜度為O(E)，否則復雜度不會降低。
空間復雜度:這個算法需要壹個二進制堆及其反向指針，還需要保存距離，所以使用的空間是3V。如果保存路徑是4V。
具體思路:首先將所有的點插入堆中，將值賦為最大值(maxint/maxlongint)，將原點值賦為0，通過relax技術更新並設置為expansion。
╝②
╔
c代碼
int GraphDijk(結構圖*g，int根，int *父，int *距離)
{
//將除根節點以外的所有點放入堆中，並將所有鍵設置為無窮大。
//遍歷根節點發送的邊，將其最短路徑設置為對應的權重，維護heap屬性。
// RemoveTop，此節點已采用最短路徑。如果是無窮大，算法將終止。
//否則，將其狀態設置為已標記，並將其設置為根節點。
//循環返回
parent[root]= root；
int reflection[g->v]；
int heap _ real[g-& gt；v-1]；
for (int i=0，j = 0；我& ltg-& gt；五；i++) {
if (i == root) {
距離[I]= 0；
}否則{
距離[i] =無窮大；
heap _ real[j++]= I；
反射[I]= j；
}
}
結構邊緣* e；
struct list _ t * iter
int * heap = heap _ real-1；
int base = 0；/* euqal到距離[root] */
int size = g-& gt；v-1；
int長度；
做{
ITER = list _ next(& amp；(g->；頂點+根)->；鏈接)；
for(；iteriter = list_next(iter)) {
e = list_entry(iter，struct Edge，link)；
長度=基數+e-& gt；重量；
if(長度& lt距離[e->；到]) {
HeapDecreaseKey(堆，大小，
距離，倒影，
反射[e->；to]，長度)；
parent[e-& gt；to]= root；
}
}
root = HeapRemoveTop(堆、大小、距離、反射)；
base =距離[根]；
if(距離[根] ==無窮大){
/*堆中的剩余節點不可訪問*/
返回g-& gt；V -(大小+1)；/*返回強連接分支節點的數量*/
}
} while(大小)；
/*成功結束算法m */
返回g-& gt；五；
}
╝④
再給壹個體會
╔
c代碼
/*裸水的最短路徑，練習二進制堆優化的Dijstra~
用二進制堆優化的Prim，前後調試了八個多小時，敲了幾次，還是沒有成功。
不過還好我熟悉優先級隊列的操作。
十幾天後的今天，我又想起了這個，終於把堆優化的Dijstra拿出來了。了解之後還挺簡單的。
有些寫方法並不是最優的，比如在堆的實現中可以減少交換元素。但是有這個我自己寫的AC
Dijkstra之後，以後寫二進制堆優化的Prim/Dijkstra和其他優先級隊列主題的時候可以和Debug對比壹下。
2011-07-24 23:00
*/
# include & ltstdio.h & gt
#定義MAXN 1200
#定義MAXM 1200000
#定義INF 19930317
結構節點
{
int d，v，p；
} heap[MAXN]；
int pos[MAXN]，HL；
int e[MAXM]，cost[MAXM]，next[MAXM]，g[MAXN]，size
int m，n，s，t；
void insert(int u，int v，int w)
{
e[++ size]= v；
next[size]= g[u]；
成本[大小]= w；
g[u] =大小；
}
void swap(int a，int b)
{
heap[0]= heap[a]；
heap[a]= heap[b]；
heap[b]= heap[0]；
堆。v]= a；
堆。v]= b；
}
無效堆積()
{
int I = 2；
while(我& lt= hl)
{
如果((i & lthl)和amp& amp(堆[i + 1]。d & lt堆[我]。d))
i++；
if(堆[i]。d & lt堆[I & gt；& gt1].d)
{
swap(i，i & gt& gt1);
我& lt& lt= 1;
}
其他
打破；
}
}
無效減少(int i)
{
而((我！= 1)；& amp(堆[我]。d & lt堆[I & gt；& gt1].d))
{
swap(i，i & gt& gt1);
我& gt& gt= 1;
}
}
void relax(int u，int v，int w)
{
if (w + heap[pos[u]]。d & lt堆，堆。d)
{
堆，堆。p = u；
堆，堆。d = w + heap[pos[u]]。d；
減少(位置[v])；
}
}
void delete_min()
{
掉期(1，HL)；
HL-；
heap fy()；
}
void初始化()
{
int u，v，w，I；
scanf("%d%d "，& ampm & amp；n)；
for(I = 1；我& lt= m；i++)
{
scanf("%d%d%d "，& ampu & amp；v，& ampw)；
插入(u，v，w)；
插入(v，u，w)；
}
s = 1；
t = n；
}
int dijkstra()
{
int u，p，I；
for(I = 1；我& lt= n；i++)
{
堆[我]。v = pos[I]= I；
堆[我]。d = INF
}
堆。p = s；
堆。d = 0；
swap(1，s)；
HL = n；
白色(hl)
{
u = heap[1]。五；
delete _ min()；
p = g[u]；
while (p)
{
if(pos[e[p]]& lt；= hl)
relax(u，e[p]，cost[p])；
p = next[p]；
}
}
}
int main()
{
init()；
Dijkstra()；
printf("%d\n "，heap[pos[t]]。d)；
返回0；
}
╝③
╔
斐波那契反應器實現
同理，斐波那契堆可以把復雜度降低到O(E+VlogV)，但是實現起來比較麻煩。因此，此處不壹壹列舉。