dijkstra算法表格怎么画数学建模
发布网友
发布时间:2022-05-02 04:31
我来回答
共1个回答
热心网友
时间:2022-06-28 06:22
在松弛时用一个pre数组记录中间结点为前一个结点
pre数组初始化为-1
//单源最短路径,dijkstra算法,邻接阵形式,复杂度o(n^2)
//求出源s到所有点的最短路径,传入图的顶点数n,(有向)邻接矩阵mat
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
#define maxn 200
#define inf 1000000000
typedef int elem_t;
void dijkstra(int n,elem_t mat[][maxn],int s,elem_t* min,int* pre){
int v[maxn],i,j,k;
for (i=0;i