本文目录一览：
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("%dn",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);
}