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