[原]所有路径的最短距离(c语言)

陈文浩 17/12/04 21:24:51

这里写图片描述

#include<stdio.h>
#define MAX 6
int n = MAX;
int cost[][MAX] = 
{
    {   0,  50,  10,1000,  45,1000},
    {1000,   0,  15,1000,  10,1000},
    {  20,1000,   0,  15,1000,1000},
    {1000,  20,1000,   0,  35,1000},
    {1000,1000,  30,1000,   0,1000},
    {1000,1000,1000,   3,1000,   0}
};//各个点的值
int distance[MAX][MAX]={0};//最终距离
void allcosts(int cost[][MAX],int distance[][MAX],int n);
int main()
{
    allcosts(cost,distance,n);
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            printf("%d ",distance[i][j]);
        }
        putchar('\n');
    }
}
void allcosts(int cost[][MAX],int distance[][MAX],int n)
{
   for(int i = 0;i < n;i++) 
        for(int j = 0;j < n;j++)
            distance[i][j] = cost[i][j];
    for(int k = 0;k < n;k++)
    //和单源一样,k相当于一个中间点,i到k最短加上k到j最短,就是i到j最短
        for(int i = 0;i < n ;i++)
            for(int j = 0;j < n;j++)
            {
                if(distance[i][k]+distance[k][j] < distance[i][j])
                    distance[i][j] = distance[i][k] + distance[k][j];
            }
}

这里写图片描述

作者:m0_37787222 发表于2017/12/4 21:24:51 原文链接
阅读:1 评论:0 查看评论