写一个最短路径算法的C代码
时间: 2023-03-14 17:15:47 浏览: 60
//答案:
#include <stdio.h>
#define MAX_VERTEX_NUM 20 //最大顶点数量
#define VRType int //顶点之间的关系类型
#define InfoType char //顶点信息类型
#define VertexType int //顶点类型
#define INFINITY 65535 //∞
//最短路径算法
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix *P, ShortPathTable *D)
{
int v,w,k,min;
//初始化
for(v=0; v<G.numVertexes; v++)
{
(*D)[v] = G.arc[v0][v];
(*P)[v] = 0;
}
(*D)[v0] = 0;
(*P)[v0] = 1;
//开始主循环,每次求得v0到某个顶点v的最短路径,并加v到集合S中
for(v=1; v<G.numVertexes; v++)
{
min = INFINITY;
for(w=0; w<G.numVertexes; w++)
{
if(!(*P)[w] && (*D)[w]<min)
{
k=w;
min = (*D)[w];
}
}
(*P)[k] = 1;
for(w=0; w<G.numVertexes;w++)
{
if(!(*P)[w] && (min + G.arc[k][w] < (*D)[w]))
{
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}