最短路徑dijkstra演算法c

Ⅰ 用C或C++實現求最短路徑的Dijkstra演算法

/* 用鄰接矩陣表示的圖的Dijkstra演算法的源程序*/

#include<stdio.h>
#define MAXVEX 100

typedef char VexType;

typedef float AdjType;

typedef struct

{ VexType vexs[MAXVEX]; /* 頂點信息 */

AdjType arcs[MAXVEX][MAXVEX]; /* 邊信息 */

int n; /* 圖的頂點個數 */

}GraphMatrix;

GraphMatrix graph;

typedef struct {

VexType vertex; /* 頂點信息 */

AdjType length; /* 最短路徑長度 */

int prevex; /* 從v0到達vi(i=1,2,…n-1)的最短路徑上vi的前趨頂點 */

}Path;

Path dist[6]; /* n為圖中頂點個數*/

#define MAX 1e+8

void init(GraphMatrix* pgraph, Path dist[])

{
int i; dist[0].length=0; dist[0].prevex=0;
dist[0].vertex=pgraph->vexs[0];

pgraph->arcs[0][0]=1; /* 表示頂點v0在集合U中 */

for(i=1; i<pgraph->n; i++) /* 初始化集合V-U中頂點的距離值 */

{ dist[i].length=pgraph->arcs[0][i];

dist[i].vertex=pgraph->vexs[i];

if(dist[i].length!=MAX)

dist[i].prevex=0;

else dist[i].prevex= -1;

}

}

void dijkstra(GraphMatrix graph, Path dist[])
{ int i,j,minvex; AdjType min;
init(&graph,dist); /* 初始化，此時集合U中只有頂點v0*/
for(i=1; i<graph.n; i++)
{ min=MAX; minvex=0;
for(j=1; j<graph.n; j++)
if( (graph.arcs[j][j]==0) && (dist[j].length<min) ) /*在V-U中選出距離值最小頂點*/
{ min=dist[j].length; minvex=j; }
if(minvex==0) break; /* 從v0沒有路徑可以通往集合V-U中的頂點 */
graph.arcs[minvex][minvex]=1; /* 集合V-U中路徑最小的頂點為minvex */
for(j=1; j<graph.n; j++) /* 調整集合V-U中的頂點的最短路徑 */
{ if(graph.arcs[j][j]==1) continue;
if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j])
{ dist[j].length=dist[minvex].length+graph.arcs[minvex][j];
dist[j].prevex=minvex;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
}
}
}

void initgraph()
{
int i,j;
graph.n=6;
for(i=0;i<graph.n;i++)
for(j=0;j<graph.n;j++)
graph.arcs[i][j]=(i==j?0:MAX);
graph.arcs[0][1]=50;
graph.arcs[0][2]=10;
graph.arcs[1][2]=15;
graph.arcs[1][4]=5;
graph.arcs[2][0]=20;
graph.arcs[2][3]=15;
graph.arcs[3][1]=20;
graph.arcs[3][4]=35;
graph.arcs[4][3]=30;
graph.arcs[5][3]=3;
graph.arcs[0][4]=45;
}

int main()
{
int i;
initgraph();
dijkstra(graph,dist);
for(i=0;i<graph.n;i++)
printf("(%.0f %d)",dist[i].length,dist[i].prevex);
return 0;
}
這個稍作改動就可以了。

Ⅱ 最短路徑 - Dijkstra演算法

演算法每次都查找距離起始點最近的點，那麼剩下的點距離起始點的距離一定比當前點大。

1.選定A節點並初始化，如上述步驟3所示

2.執行上述 4、5兩步驟，找出U集合中路徑最短的節點D 加入S集合，並根據條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合

3.這時候 A->B, A->C 都為3，沒關系。其實這時候他倆都是最短距離，如果從演算法邏輯來講的話，會先取到B點。而這個時候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) ，如圖所示這時候A->B距離 其實為 A->D->B

思路就是這樣，往後就是大同小異了
演算法結束

（圖片來源於網路）

Dijkstra演算法保證能找到一條從初始點到目標點的最短路徑，只要所有的邊都有一個非負的代價值。在上圖中，粉紅色的結點是初始結點，藍色的是目標點，而類菱形的有色區域則是Dijkstra演算法掃描過的區域。顏色最淡的區域是那些離初始點最遠的，因而形成探測過程（exploration）的邊境（frontier）。因而Dijkstra演算法可以找到一條最短的路徑，但是效率上並不高。

數據結構--Dijkstra演算法最清楚的講解

Ⅲ dijkstra演算法是什麼

dijkstra演算法最短路徑演算法。

Dijkstra是典型最短路徑演算法，用於計算一個節點到其他節點的最短路徑。該演算法使用的是貪心策略：每次都找出剩餘頂點中與源點距離最近的一個頂點。

給定一帶權圖，圖中每條邊的權值是非負的，代表著兩頂點之間的距離。指定圖中的一頂點為源點，找出源點到其它頂點的最短路徑和其長度的問題，即是單源最短路徑問題。

Dijkstra的原理

（1）初始化時，S只含有源節點。

（2）從U中選取一個距離v最小的頂點k加入S中（該選定的距離就是v到k的最短路徑長度）。

（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源節點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值是頂點k的距離加上k到u的距離。

Ⅳ dijkstra演算法是什麼

Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。

其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。

不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。

因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。

Ⅳ 用C++求dijkstra演算法求最短路徑

/**************************************************************
* 給定一個帶權有向圖G = (V，E)，其中每條邊的權是一個非負整數。*
* 另外還給定V中的一個頂點，稱為源。現在我們要計算從源到所有其 *
* 他各頂點的最短路長度。這里路徑長度是路上各邊權之和。這個問 *
* 題通常稱為單源最短路徑問題。 *
***************************************************************/
#include<iostream.h>

#define INFINITE 100

void main()
{
int j,i,n,k,t,**w,*s,*p,*d;

cout<<"input the value of n:";
cin>>n;
cout<<endl;

d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];

for(i = 0; i < n; i++)
{
w[i] = new int[n];
}

for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
cin>>w[i][j];

for(s[0] = 1,i = 1; i < n; i++)
{
s[i] = 0;
d[i] = w[0][i];
if(d[i] < INFINITE)
p[i]=0;
else
p[i]=-1;
}

for(i = 1; i < n; i++)
{
t = INFINITE;
k = 1;
for(j = 1; j < n; j++)
if((!s[j]) && (d[j] < t))
{
t = d[j];
k = j;
}
s[k]=1;//point k join the S
for (j = 1; j < n; j++)
if((!s[j]) && (d[j] > d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j];
p[j] = k;
}

}
cout<<"從源點到其它頂點的最短距離依次如下：";
for(i=1;i<n;i++) cout<<d[i]<<" ";
cout<<endl;

}
/*********
頂點個數用n表示，這里給出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具體例子見 電子工業出版社 《演算法設計技巧與分析》148頁
************/

Ⅵ 數學建模第四章 圖論 part4.2最短路徑問題-Dijkstra演算法

1.Dijkstra演算法介紹

演算法特點：

迪科斯徹演算法使用了廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

演算法的思路

Dijkstra演算法採用的是一種貪心的策略，聲明一個數組dis來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合：T，初始時，原點 s 的路徑權重被賦為 0 （dis[s] = 0）。若對於頂點 s 存在能直接到達的邊（s,m），則把dis[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。初始時，集合T只有頂點s。 

然後，從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，並且把該點加入到T中，OK，此時完成一個頂點， 

然後，我們需要看看新加入的頂點是否可以到達其他頂點並且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那麼就替換這些頂點在dis中的值。 

然後，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

2、Dijkstra演算法示例演示

我求下圖，從頂點v1到其他各個頂點的最短路徑.

首先第一步，我們先聲明一個dis數組，該數組初始化的值為：

我們的頂點集T的初始化為：T={v1}

既然是求 v1頂點到其餘各個頂點的最短路程，那就先找一個離 1 號頂點最近的頂點。通過數組 dis 可知當前離v1頂點最近是 v3頂點。當選擇了 2 號頂點後，dis[2]（下標從0開始）的值就已經從「估計值」變為了「確定值」，即 v1頂點到 v3頂點的最短路程就是當前 dis[2]值。將V3加入到T中。 

為什麼呢？因為目前離 v1頂點最近的是 v3頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 v1頂點到 v3頂點的路程進一步縮短了。因為 v1頂點到其它頂點的路程肯定沒有 v1到 v3頂點短.

OK，既然確定了一個頂點的最短路徑，下面我們就要根據這個新入的頂點V3會有出度，發現以v3 為弧尾的有： < v3,v4 >,那麼我們看看路徑：v1–v3–v4的長度是否比v1–v4短，其實這個已經是很明顯的了，因為dis[3]代表的就是v1–v4的長度為無窮大，而v1–v3–v4的長度為：10+50=60，所以更新dis[3]的值,得到如下結果： 

因此 dis[3]要更新為 60。這個過程有個專業術語叫做「鬆弛」。即 v1頂點到 v4頂點的路程即 dis[3]，通過 < v3,v4> 這條邊鬆弛成功。這便是 Dijkstra 演算法的主要思想：通過「邊」來鬆弛v1頂點到其餘各個頂點的路程。

然後，我們又從除dis[2]和dis[0]外的其他值中尋找最小值，發現dis[4]的值最小，通過之前是解釋的原理，可以知道v1到v5的最短距離就是dis[4]的值，然後，我們把v5加入到集合T中，然後，考慮v5的出度是否會影響我們的數組dis的值，v5有兩條出度：< v5,v4>和 < v5,v6>,然後我們發現：v1–v5–v4的長度為：50，而dis[3]的值為60，所以我們要更新dis[3]的值.另外，v1-v5-v6的長度為：90，而dis[5]為100，所以我們需要更新dis[5]的值。更新後的dis數組如下圖： 

然後，我們使用同樣原理，分別確定了v6和v2的最短路徑，最後dis的數組的值如下： 

因此，從圖中，我們可以發現v1-v2的值為：∞，代表沒有路徑從v1到達v2。所以我們得到的最後的結果為：

Ⅶ 用dijkstra演算法解決最短路徑問題c語言代碼實現時怎樣將每一個路徑的頂點次序依次輸出出來

voidDijkstra(intn,intv,intdist[],intprev[],int**cost)
{
inti;
intj;
intmaxint=65535;//定義一個最大的數值，作為不相連的兩個節點的代價權值
int*s;//定義具有最短路徑的節點子集s
s=(int*)malloc(sizeof(int)*n);
//初始化最小路徑代價和前一跳節點值
for(i=1;i<=n;i++)
{
dist[i]=cost[v][i];
s[i]=0;
if(dist[i]==maxint)
{
prev[i]=0;
}
else
{
prev[i]=v;
}
}
dist[v]=0;
s[v]=1;//源節點作為最初的s子集
for(i=1;i<n;i++)
{
inttemp=maxint;
intu=v;
//加入具有最小代價的鄰居節點到s子集
for(j=1;j<=n;j++)
{
if((!s[j])&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
}
s[u]=1;
//計算加入新的節點後，更新路徑使得其產生代價最短
for(j=1;j<=n;j++)
{
if((!s[j])&&(cost[u][j]<maxint))
{
intnewdist=dist[u]+cost[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
}
}
//展示最佳路徑函數
voidShowPath(intn,intv,intu,int*dist,int*prev)
{
intj=0;
intw=u;
intcount=0;
int*way;
way=(int*)malloc(sizeof(int)*(n+1));
//回溯路徑
while(w!=v)
{
count++;
way[count]=prev[w];
w=prev[w];
}
//輸出路徑
printf("thebestpathis:
");
for(j=count;j>=1;j--)
{
printf("%d->",way[j]);
}
printf("%d
",u);
}
//主函數，主要做輸入輸出工作
voidmain()
{
inti,j,t;
intn,v,u;

int**cost;//代價矩陣
int*dist;//最短路徑代價
int*prev;//前一跳節點空間
printf("pleaseinputthenodenumber:");
scanf("%d",&n);
printf("pleaseinputthecoststatus:
");

cost=(int**)malloc(sizeof(int)*(n+1));
for(i=1;i<=n;i++)
{
cost[i]=(int*)malloc(sizeof(int)*(n+1));
}
//輸入代價矩陣
for(j=1;j<=n;j++)
{
for(t=1;t<=n;t++)
{
scanf("%d",&cost[j][t]);
}
}

dist=(int*)malloc(sizeof(int)*n);
prev=(int*)malloc(sizeof(int)*n);
printf("pleaseinputthesourcenode:");
scanf("%d",&v);
//調用dijkstra演算法
Dijkstra(n,v,dist,prev,cost);
printf("*****************************
");
printf("haveconfirmthebestpath
");
printf("*****************************
");
for(i=1;i<=n;i++)
{
if(i!=v)
{
printf("thedistancecostfromnode%dtonode%dis%d
",v,i,dist[i]);
printf("thepre-nodeofnode%disnode%d
",i,prev[i]);
ShowPath(n,v,i,dist,prev);
}
}
}