// 每对顶点间的最短距离Floyd_Warshall算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
#define Infinity 65535
#define NIL 65535
using namespace std;
//d
int d1[MAX][MAX];
int d2[MAX][MAX];
//用来存储边的权值,即有向图的邻接矩阵
int w[MAX][MAX];
//
int parent1[MAX][MAX];
int parent2[MAX][MAX];
//初始化,把w[i][j]赋给d[i][j]
void initialise(int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d1[i][j] = w[i][j];
}
//求所有对顶点之间的最短距离
void Floyd_Warshall(int n)
{
initialise(n);
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(d1[i][j]<=(d1[i][k]+d1[k][j]))
{
d2[i][j] = d1[i][j];
parent2[i][j] = parent1[i][j];
}
else
{
d2[i][j] = (d1[i][k]+d1[k][j]);
parent2[i][j] = parent1[k][j];
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
d1[i][j] = d2[i][j];
parent1[i][j] = parent2[i][j];
}
}
}
void print_i_to_j(int i,int j)
{
int p = parent1[i][j];
if(p==NIL)
{
cout<<"顶点"<<j<<" ";
return;
}
else
{
print_i_to_j(i,p);
cout<<"顶点"<<j<<" ";
}
}
void print(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<parent1[i][j]<<" ";
cout<<endl;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例的个数:"<<endl;
cin>>cases;
while(cases--)
{
cout<<"请输入顶点个数:"<<endl;
int n;
cin>>n;
cout<<"请输入邻接矩阵(n*n)(如果二点之间没有有向线段,输入65535):"<<endl;
int i,j;
//二点之间没有有向线段,输入65535
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>w[i][j];
if(w[i][j]==0||w[i][j]==65535)
parent1[i][j] = NIL;
else
parent1[i][j] = i;
}
Floyd_Warshall(n);
cout<<"输出每一对顶点间的最短距离:"<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短距离为:"<<d1[i][j]<<endl;
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短路径为:"<<endl;
print_i_to_j(i,j);
cout<<endl;
}
}
system("pause");
return 0;
}
----------------------------------------程序测试-----------------------------------------------
请输入案例的个数:
1
请输入顶点个数:
5
请输入邻接矩阵(n*n)(如果二点之间没有有向线段,输入65535):
0 3 8 65535 -4
65535 0 65535 1 7
65535 4 0 65535 65535
2 65535 -5 0 65535
65535 65535 65535 6 0
输出每一对顶点间的最短距离:
顶点1到顶点1的最短距离为:0
顶点1到顶点1的最短路径为:
顶点1
顶点1到顶点2的最短距离为:1
顶点1到顶点2的最短路径为:
顶点1 顶点5 顶点4 顶点3 顶点2
顶点1到顶点3的最短距离为:-3
顶点1到顶点3的最短路径为:
顶点1 顶点5 顶点4 顶点3
顶点1到顶点4的最短距离为:2
顶点1到顶点4的最短路径为:
顶点1 顶点5 顶点4
顶点1到顶点5的最短距离为:-4
顶点1到顶点5的最短路径为:
顶点1 顶点5
顶点2到顶点1的最短距离为:3
顶点2到顶点1的最短路径为:
顶点2 顶点4 顶点1
顶点2到顶点2的最短距离为:0
顶点2到顶点2的最短路径为:
顶点2
顶点2到顶点3的最短距离为:-4
顶点2到顶点3的最短路径为:
顶点2 顶点4 顶点3
顶点2到顶点4的最短距离为:1
顶点2到顶点4的最短路径为:
顶点2 顶点4
顶点2到顶点5的最短距离为:-1
顶点2到顶点5的最短路径为:
顶点2 顶点4 顶点1 顶点5
顶点3到顶点1的最短距离为:7
顶点3到顶点1的最短路径为:
顶点3 顶点2 顶点4 顶点1
顶点3到顶点2的最短距离为:4
顶点3到顶点2的最短路径为:
顶点3 顶点2
顶点3到顶点3的最短距离为:0
顶点3到顶点3的最短路径为:
顶点3
顶点3到顶点4的最短距离为:5
顶点3到顶点4的最短路径为:
顶点3 顶点2 顶点4
顶点3到顶点5的最短距离为:3
顶点3到顶点5的最短路径为:
顶点3 顶点2 顶点4 顶点1 顶点5
顶点4到顶点1的最短距离为:2
顶点4到顶点1的最短路径为:
顶点4 顶点1
顶点4到顶点2的最短距离为:-1
顶点4到顶点2的最短路径为:
顶点4 顶点3 顶点2
顶点4到顶点3的最短距离为:-5
顶点4到顶点3的最短路径为:
顶点4 顶点3
顶点4到顶点4的最短距离为:0
顶点4到顶点4的最短路径为:
顶点4
顶点4到顶点5的最短距离为:-2
顶点4到顶点5的最短路径为:
顶点4 顶点1 顶点5
顶点5到顶点1的最短距离为:8
顶点5到顶点1的最短路径为:
顶点5 顶点4 顶点1
顶点5到顶点2的最短距离为:5
顶点5到顶点2的最短路径为:
顶点5 顶点4 顶点3 顶点2
顶点5到顶点3的最短距离为:1
顶点5到顶点3的最短路径为:
顶点5 顶点4 顶点3
顶点5到顶点4的最短距离为:6
顶点5到顶点4的最短路径为:
顶点5 顶点4
顶点5到顶点5的最短距离为:0
顶点5到顶点5的最短路径为:
顶点5
请按任意键继续. . .
分享到:
相关推荐
Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法)
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
Floyd-Warshall算法是一种计算图中所有顶点对之间的最短路径的动态规划算法。其基本思想是通过逐步考虑所有顶点作为中间点来更新最短路径。ISOMAP(Isometric Mapping)是一种非线性降维方法,它使用最短路径距离来...
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。采用C++实现
弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题。该程序包括函数,主函数,以及打印出最短路径。
最短路径_Floyd算法_matlab实现.doc
最短路径(Floyd-Warshall)
使用c++编写的floyd-warshall算法,还有《算法导论》上的另外一种动态规划解法。
Floyd_Floydmatlab_最短路径算法_源码
floyd计算最短路径,只需要更改邻接矩阵
Floyd_warshall的Java代码及详细注释
使用floyd warshall算法求图中任意两点间最短路径 graph shortest path
最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现
佛洛依德算法用于加权最短路径,可直接调用。
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现, 有注释,简单...
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
本节内容王道考研/CSKAOYAN.COM最短路径Floyd算法王道考研/CSKAOYAN.COM罗伯特·弗洛伊德1978年图灵奖得主• Floyd算法(Flo
在得到距离矩阵D=[dij]m*n后,通过Floyd算法快速获得D的最短距离矩阵D*。
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。