返回顶部

收藏

每对结点之间最短路径的C++实现

更多
#include <iostream>
using namespace std;

const int MaxSize=10;

int arr[MaxSize][MaxSize]; //起始的邻接矩阵
int dist[MaxSize][MaxSize]; //保存每对结点之间的最短路径

int numNode=0;

//创建邻接矩阵
void createArr()
{
    cin>>numNode;
    for(int i=0;i<numNode;++i)
        for(int j=0;j<numNode;++j)
            cin>>arr[i][j];
}

//求出每对结点之间的最短路径
void allPath()
{
    //初始化dist数组
    for(int i=0;i<numNode;++i)
        for(int j=0;j<numNode;++j)
            dist[i][j]=arr[i][j];

    //迭代:对于结点k,若i直接到j的距离大于i经过k再到j的距离和时,
    //则改写i到j的距离
    for(int k=0;k<numNode;++k)
        for(int i=0;i<numNode;++i)
            for(int j=0;j<numNode;++j)
                if(dist[i][k]+dist[k][j]<dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
}

int main()
{
    createArr();

    allPath();
}

标签:最短路径,算法,C++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  2. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  3. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  4. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  5. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  6. espace 发表 2015-07-18 17:43:14 Two Sum
  7. bystander 发表 2013-04-01 10:12:37 [藏]关于B树的一篇文章
  8. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  9. lvfuyu 发表 2015-04-12 08:53:30 [hihocoder]矩阵快速幂
  10. leaver 发表 2013-05-27 02:55:49 求整数1-N范围和为N的所有组合
  11. lvfuyu 发表 2015-04-18 09:13:32 [hihocoder]二分查找
  12. cijianzy 发表 2015-05-01 14:20:33 修复了中文维基百科基数排序C++代码的一个bug

发表评论