djisktra演算法java,djisktra演算法可求出非負賦權圖中一頂點的最短距離

本文目錄一覽：

• 1、Djisktra演算法能否求有負權的有向圖中兩點間的最短路徑，舉例說明。
• 2、用堆來實現計算單源最短路的迪傑斯特拉(Djisktra)演算法

Djisktra演算法能否求有負權的有向圖中兩點間的最短路徑，舉例說明。

不能。比如n=3，鄰接矩陣：0，3，43，0，-24，-2，0求d[1,2]為3，實際為2

用堆來實現計算單源最短路的迪傑斯特拉(Djisktra)演算法

//最近剛寫了這個程序，希望對你有幫助

#includestdafx.h

#includestdio.h

#includestdlib.h

#define MAXNODE 30 //定義最大節點數

#define MAXCOST 1000 //如果兩點間無路勁，則設MAXCOST

int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=6; //為實際節點數

//dijkstra演算法求單源最短路徑，這個函數就沒加註釋了，需要自己理解。

void dijkstra(int v0) //v0為起始節點

{

int s[MAXNODE];

int mindis,dis,i,j,u;

for(i=1;i=n;i++)

{

dist[i]=cost[v0][i];

s[i]=0;

}

s[v0]=1;

for(i=1;i=n;i++)

{

mindis=MAXCOST;

for(j=1;j=n;j++)

{

if(s[j]==0 dist[j]mindis)

{

u=j;

mindis=dist[j];

}

}

s[u]=1;

for(j=1;j=n;j++)

if(s[j]==0)

{

dis=dist[u]+cost[u][j];

dist[j]=(dist[j]dis)?dist[j]:dis;

}

}

}

//自定義display_path函數，輸出各頂點最短路徑

void display_path(int v0)

{

int i;

printf(“\n頂點 %d 到各頂點的最短路徑長度如下:\n”,v0);

for(i=1;i=n;i++)

{

printf(” (v%d-v%d):”,v0,i);

if(dist[i]==MAXCOST)

printf(“無路徑”);

else

printf(“%d\n”,dist[i]);

}

}

//主函數中各個定點的cost值可以根據實際路勁修改

void main()

{

int i,j,v0=1;

for(i=1;i=n;i++)

for(j=1;j=n;j++)

cost[i][j]=((i==j)?0:MAXCOST);

cost[1][2]=10;

cost[1][4]=30;

cost[1][5]=100;

cost[1][6]=20;

cost[2][3]=50;

cost[3][5]=10;

cost[4][3]=20;

cost[4][5]=60;

cost[5][6]=30;

dijkstra(v0);

display_path(v0);

}