求有向图Djistra算法C/C++代码

发布网友发布时间：2022-04-26 09:17

共4个回答

热心网友时间：2022-06-26 14:22

参考

/*===============================================

单源最短路径

Dijkstra 算法

适用条件：所有边的权非负

!!注意：
1.输入的图的权必须非负
2.顶点标号从0开始
3.当i,j不相邻时G[i,j]=infinity

================================================*/
int Dijkstra(Graph G,int n,int s,int t, int path[])
{
int i,j,w,minc, d[max_vertexes], mark[max_vertexes];
for (i=0; i<n; i++) mark[i]=0;

for (i=0; i<n; i++)
{
d[i]=G[s][i];
path[i]=s;
}

mark[s]=1; path[s]=0; d[s]=0;

for(i=1; i<n; i++)
{
minc = infinity;
w = 0;
for( j = 0; j < n; j++ )
if( ( mark[j]==0 ) && ( minc >= d[j] ) ) {
minc=d[j];w=j;
}
mark[w]=1;
for(j=0; j<n; j++)
if( (mark[j]==0) && ( G[w][j] != infinity ) && ( d[j] > d[w]+G[w][j] ) )
{
d[j]=d[w]+G[w][j];
path[j]=w;
}
}
return d[t];
}

热心网友时间：2022-06-26 14:23

先对20个顶点标号，然后建立一个20*20的矩阵，表示这20个顶点的连通关系。然后再用Dijkstra求解之。

热心网友时间：2022-06-26 14:23

临接矩阵怎么是m*n的，是省略了对角线的0吗？能说清楚一点吗？还有你给的示例的点坐标是怎么回事？

参考资料：如果您的回答是从其他地方引用，请表明出处

热心网友时间：2022-06-26 14:24

PASCAL的