求图的任两结点间的距离

来源：百度知道 编辑：UC知道 时间：2024/05/21 05:39:25
求图的任两结点间的距离
一: 实验目的
掌握按动态规划原理解决计算图的任两结点间的距离的Floyd算法
二:问题描述
设图G 的结点个数n=10,给定一个10*10矩阵作为图G 的成本矩阵.
其中的元素99相当于8，表示相应的两个结点间没有边相连
0 99 8 7 6 5 4 3 2 1
99 0 99 8 7 6 5 4 3 2
8 99 0 99 8 7 6 5 4 3
7 8 99 0 99 8 7 6 5 4
C＝ 6 7 8 99 0 99 8 7 6 5
5 6 7 8 99 0 99 8 7 6
4 5 6 7 8 99 0 99 8 7
3 4 5 6 7 8 99 0 99 8
2 3 4 5 6 7 8 99 0 99
1 2 3 4 5 6 7 8 99 0
三. 基本要求
(2) 用二维数组存放C和A ，C是原成本矩阵，A 是求出的距离矩阵
(3) 算法采用三重循环，其中最外层的循环变量必须代表中间结点，中层的循环变量代表头结点而内层循环变量代表尾结点。
(4) 试着把三层循环变量的顺序作些改变，最外层的循环变量仍代表中间结点，而中层循环变量代表尾结点，内层循环变量代表头结点。把两种做法所得结果作比较,看结果是否相同

#include <iostream>
using namespace std;
int main(){
int n=10,dist[10][10];
int map[10][10]={
{0,99,8,7,6,5,4,3,2,1},
{99,0,99,8,7,6,5,4,3,2},
{8,99,0,99,8,7,6,5,4,3},
{7,8,99,0,99,8,7,6,5,4},
{6,7,8,99,0,99,8,7,6,5},
{5,6,7,8,99,0,99,8,7,6},
{4,5,6,7,8,99,0,99,8,7},
{3,4,5,6,7,8,99,0,99,8},
{2,3,4,5,6,7,8,99,0,99},
{1,2,3,4,5,6,7,8,99,0}
};
int i,j,k,u,v;

for(k=0;k<n;k++)//代表中间结点
for(i=0;i<n;i++)//代表头结点
for(j=0;j<n;j++)//代表尾结点
if((map[i][k]+map[k][j]) < map[i][j])
map[i][j] = map[i][k]+map[k][j];
//输出
for( u=0;u<10;u++){
int count=0;
for( v=0;v<10;v++){
cout<<map[u][v]<<" ";
count