用Dijkstra算法求最短路径

发布网友发布时间：2022-05-20 09:54

共1个回答

热心网友时间：2023-10-15 19:13

#include <stdio.h>
#include <string.h>
#define MAX 20
int mincost(int V[], int D[], int n);
int main()
{
int C[MAX][MAX];
int D[MAX], V[MAX] = { 0 }; /*数组V用来表示每次计算加入集合V的点，1为加入了，0为还没有加入*/
int n, i, j, k, w, sum;
printf("请输入顶点个数:");
scanf("%d", &n);
printf("\n请输入建立后的临接矩阵(用n*n矩阵表示), 输入100000表示无穷大:\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &C[i][j]);
}
}
V[1] = 1; /*1为源点*/
for(i = 1; i <= n; i++)
{
D[i] = C[1][i]; /*D置初值*/
}
for(i = 1; i <= n; i++)
{
/*从集合S(即没有经过计算的点）中选出一个点w（即V中值为0），使D[w]值最小*/
w = mincost(V, D, n);
V[w] = 1;
/*由于w的选定，S中的每个点(即V中值为0的点都要重新计算其到源点的最小值*/
for(k = 2; k <= n; k++)
{
if(V[k] == 0)
{
sum = D[w] + C[w][k];
if(sum < D[k])
{
D[k] = sum;
}
}
}
}
for(i = 2; i <= n; i++)
{
printf("D[%d] = %d\n", i, D[i]);
}
memset(V, 0, MAX * sizeof(int)); /*初始化*/
return 0;
}

int mincost(int V[], int D[], int n)
{
int temp = 10000000, i, w = 2;
for(i = 2;i <= n; i++)
{
if(V[i] == 0 && D[i] < temp)
{
temp = D[i];
w = i;
}
}
return w;
}

改成文件的就行了