// 每对顶点间的最短路径.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
#define Infinity 65535
using namespace std;
//L2[i][j]存储L1[i][j]*Lij
int L1[MAX][MAX];
int L2[MAX][MAX];
//用来存储边的权值,即有向图的邻接矩阵
int w[MAX][MAX];
//初始化,把w[i][j]赋给L1[i][j]
void initialise(int n)
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
L1[i][j] = w[i][j];
}
//求每一对顶点间暂时最短距离
void extend_shortest_paths(int n)
{
int i,j,k,l;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
L2[i][j] = Infinity;
for(k=1;k<=n;k++)
//改进
L2[i][j] = L2[i][j]<(L1[i][k]+L1[k][j])?L2[i][j]:(L1[i][k]+L1[k][j]);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
L1[i][j] = L2[i][j];
}
//求所有对顶点之间的最短距离
void show_all_pairs_shortest_paths(int n)
{
initialise(n);
int m;
for(m=2;m<=n-1;m++)
extend_shortest_paths(n);
}
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];
}
show_all_pairs_shortest_paths(n);
cout<<"输出每一对顶点间的最短距离:"<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短距离为:"<<L1[i][j]<<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到顶点2的最短距离为:1
顶点1到顶点3的最短距离为:-3
顶点1到顶点4的最短距离为:2
顶点1到顶点5的最短距离为:-4
顶点2到顶点1的最短距离为:3
顶点2到顶点2的最短距离为:0
顶点2到顶点3的最短距离为:-4
顶点2到顶点4的最短距离为:1
顶点2到顶点5的最短距离为:-1
顶点3到顶点1的最短距离为:7
顶点3到顶点2的最短距离为:4
顶点3到顶点3的最短距离为:0
顶点3到顶点4的最短距离为:5
顶点3到顶点5的最短距离为:3
顶点4到顶点1的最短距离为:2
顶点4到顶点2的最短距离为:-1
顶点4到顶点3的最短距离为:-5
顶点4到顶点4的最短距离为:0
顶点4到顶点5的最短距离为:-2
顶点5到顶点1的最短距离为:8
顶点5到顶点2的最短距离为:5
顶点5到顶点3的最短距离为:1
顶点5到顶点4的最短距离为:6
顶点5到顶点5的最短距离为:0
请按任意键继续. . .
分享到:
相关推荐
Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。采用C++实现
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现,有注释,简单轻松...
最短路径算法Dijkstra源代码,测试可以正常使用
加权图中顶点间最短路径的算法,使用C++实现Floyd算法,对正在学习算法的同学应该挺有帮助的
基于Java多线程实现所有顶点间最短路径的并行算法
试设计一个算法,求图中一个源点到其他各顶点的最短路径。 (1)用邻接表表示图; (2)按长度非递减次序打印输出最短路径的长度及相应路径。
从某个源点到其于各顶点的最短路径,单源点最短路径问题
本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其C语言实现过程。系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,...
* (有向)带权图的单源点最短路径算法 */ package dsa; public class BestFSDijkstra extends BestFS { //构造方法 public BestFSDijkstra(Graph g) { super(g); } //更新尚未访问的顶点到源点的最短距离 ...
简单介绍图的结构建立与最短路径算法,不是源代码
最短路径算法 1 假设无向图有n各顶点(n>20),随机生成任意顶点之间的边的权值,并输出其邻接矩阵; 2 使用贪心算法,求解随机选定的顶点i、j之间的距离,并输出结果; 3 实验其计算复杂度:按照从小到大多次改变n...
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历...
带权图的多种算法(有向图,无向图,Dijkstra算法,到每个顶点的最短距离,佛洛依德算法(Floyd),找出每对顶点的最短路径,带权重无向图最小生成树,prim算法,Kruskal算法求最小生成树)java实现, 有注释,简单...
并行最短路径算法Dijkstra。 为实现并行最短路径计算,我们必须要解决如下问题: (1)数据获取:利用随机函数生成大约2000个节点及其节点之间的距离。本程序使用邻接矩阵来存储带权有向图的信息。矩阵大小2000*2000...
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
利用Dijkstra算法来求解顶点之间最短路径
一个简单的最短路径算法,根据距离矩阵(内设,可更改),我写的是6*6的矩阵,也就是有6个地方,ABCDEF,输入1 2,即为求A->B的最短路径。
用Floyd算法实现求有向图中各顶点之间的最短路径及其长度
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。