Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權(quán)邊。問題描述
在無向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其余各點的最短路徑。（單源最短路徑） 迪杰斯特拉(Dijkstra)算法思想 按路徑長度遞增次序產(chǎn)生最短路徑算法： 把V分成兩組： （1）S：已求出最短路徑的頂點的集合 （2）V-S=T：尚未確定最短路徑的頂點集合 將T中頂點按最短路徑遞增的次序加入到S中， 保證：（1）從源點V0到S中各頂點的最短路徑長度都不大于 從V0到T中任何頂點的最短路徑長度 （2）每個頂點對應(yīng)一個距離值 S中頂點：從V0到此頂點的最短路徑長度 T中頂點：從V0到此頂點的只包括S中頂點作中間 頂點的最短路徑長度 依據(jù)：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的 直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和 （反證法可證） 求最短路徑步驟 算法步驟如下： 1. 初使時令 S={V0},T={其余頂點}，T中頂點對應(yīng)的距離值 若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權(quán)值 若不存在<V0,Vi>，d(V0,Vi)為∝ 2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S 3. 對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的 距離值比不加W的路徑要短，則修改此距離值 重復(fù)上述步驟2、3，直到S中包含所有頂點，即S=T為止 代碼： 源地址：
www.cnblogs.com/newwy /*********************************
* 最短路徑---Dijkstra算法實現(xiàn)
* HDU：2544
* BLOG:www.cnblogs.com/newwy
* AUTHOR:Wang Yong
**********************************/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
int dijkstra (int mat[][MAX],int n, int s,int f)
{
int dis[MAX];
int mark[MAX];//記錄被選中的結(jié)點
int i,j,k = 0;
for(i = 0 ; i < n ; i++)//初始化所有結(jié)點，每個結(jié)點都沒有被選中
mark[i] = 0;
for(i = 0 ; i < n ; i++)//將每個結(jié)點到start結(jié)點weight記錄為當(dāng)前distance
{
dis[i] = mat[s][i];
//path[i] = s;
}
mark[s] = 1;//start結(jié)點被選中
//path[s] = 0;
dis[s] = 0;//將start結(jié)點的的距離設(shè)置為0
int min ;//設(shè)置最短的距離。
for(i = 1 ; i < n; i++)
{
min = INF;
for(j = 0 ; j < n;j++)
{
if(mark[j] == 0 && dis[j] < min)//未被選中的結(jié)點中，距離最短的被選中
{
min = dis[j] ;
k = j;
}
}
mark[k] = 1;//標記為被選中
for(j = 0 ; j < n ; j++)
{
if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//修改剩余結(jié)點的最短距離
{
dis[j] = dis[k] + mat[k][j];
}
}
}
return dis[f];
}
int mat[MAX][MAX];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m))
{
int a,b,dis;
if(n == 0 || m == 0)
break;
int i,j;
for(i = 0 ; i < n;i++)
for(j = 0 ; j < n; j++)
mat[i][j] = INF;
for(i = 0 ; i < m ;i++)
{
scanf("%d %d %d",&a,&b,&dis);
--a,--b;
if(dis < mat[a][b] || dis < mat[b][a])
mat[a][b] = mat[b][a] = dis;
}
int ans = dijkstra(mat,n,0,n-1);
printf("%d\n",ans);
}
}
可用 優(yōu)先隊列優(yōu)化
其他解釋：
http://blog.csdn.net/jiahui524/article/details/6636913
posted on 2012-06-16 03:53
luis 閱讀(554)
評論(0) 編輯 收藏 引用 所屬分類:
圖論*矩陣