用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;
}
改成文件的就行了