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);

}