/*
证明next[i][j] = k;是错误的例子
Node 0 Position (4,61) nextJump -1 Neighbor [3] goodNeighbor [3]
Node 1 Position (89,19) nextJump 1 Neighbor [4, 2] goodNeighbor [4, 2]
Node 2 Position (88,74) nextJump 2 Neighbor [4, 1] goodNeighbor [4, 1]
Node 3 Position (23,85) nextJump 3 Neighbor [4, 0] goodNeighbor [4, 0]
Node 4 Position (68,59) nextJump 3 Neighbor [2, 1, 3] goodNeighbor [2, 1, 3]
*/
#include "iostream"
#include "vector"
using namespace std;
vector<int> path;
int min(int a,int b)
{
return a>b?b:a;
}
/*
int cost[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 len =0;
int cost[5][5] =
{
99,7,99,6,88,
5,99,99,4,99,
99,99,99,99,8,
9,5,99,99,7,
99,99,4,6,99
};
int best[5][5];
int next[5][5];
int nodeCount = 5;
void Floyd()
{
int i,j,k;
for(i=0;i<nodeCount;i++)
for(j=0;j<nodeCount;j++)
{
best[i][j]=cost[i][j];
next[i][j]= (i == j ? -1:i);
}
for(k =0;k<nodeCount;k++)
for(i=0;i<nodeCount;i++)
if(i != k)
{
for(j=0;j<nodeCount;j++)
{
if(j != i && j!= k && best[i][j] > best[i][k]+best[k][j])
{
best[i][j] = best[i][k]+best[k][j];
next[i][j] = next[k][j]; //按照这种方法算出来的是前驱,也就是从i到j的路径中j前边的一个顶点。
//next[i][j] = next[i][k];
//next[i][j] = k;
}
}
}
}
int nextJump(int i,int j)//返回的是节点自身
{
if(i == j)
return i;
else if( next[i][j] == -1)
return -1;
else
return nextJump(i,next[i][j]);
}
/*
利用递归的方法把从i到j的路径打印出来
*/
void printPath(int i,int j)
{
if(i == j)
cout<<i<<" ";
else if(i == -1)
cout<<"no path";
else
{
printPath(i,next[i][j]);
cout<<j<<" ";
}
}
/*
这个里边path里半存放的是从i到j得所有中间节点
*/
void savePath(int i,int j)
{
if(i == j)
path.push_back(i);
else if(i == -1)
cout<<"no path";
else
{
savePath(i,next[i][j]);
path.push_back(j);
}
}
main()
{
Floyd();
for(int i=0;i<nodeCount;i++)
{
for(int j=0;j<nodeCount;j++)
{
//cout<<nextJump(i,j)<<" ";
//cout<<next[i][j]<<" ";
path.clear();
cout<<"path "<<i<<" => "<<j<<":";
savePath(i,j);
if(path.size() > 1)
cout<<path.at(1);
else
cout <<path.at(0);
cout<<endl;
}
cout<<endl;
}
return 0;
}
分享到:
相关推荐
"Floyd_路径规划_Floyd算法_dynamicdijkstra"这一主题主要涵盖了计算机科学中的路径规划问题,特别是Floyd算法的运用以及与Dijkstra算法的比较。本文将深入探讨Floyd算法的核心思想、实现过程、适用场景以及它与动态...
**Floyd算法** Floyd算法,也称为Floyd-Warshall算法,是图论中用于查找有向图或无向图中所有顶点之间最短路径的一种经典算法。该算法由Robert Floyd在1962年提出,适用于解决多源最短路径问题,即寻找从图中的一个...
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
首先读入小区间的距离矩阵和人口数量,然后分别使用Floyd算法和Dijkstra算法计算出任意两点之间的最短距离,并基于这些结果进行后续的分析和计算。 **4.3 模型评估** 通过比较两种方法的结果,可以选择最优的选址...
"Floyd算法的知识点" Floyd算法是解决最短路问题的一种经典算法,由Floyd于1962年提出。该算法是一种权矩阵迭代算法,用于计算图中任意两节点之间的最短路。 Floyd算法的基本步骤 1. 令权矩阵D的初始值为无穷大,...
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
Floyd 算法详细教程 Floyd 算法是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵 A=[a(i,j)] n×n 开始,递归地进行 n 次...
**Floyd算法详解** Floyd算法,也被称为Floyd-Warshall算法,是图论中的一个经典算法,主要用于解决在加权图中寻找任意两个顶点之间的最短路径问题。这个算法是由美国计算机科学家Robert W. Floyd提出的,因此得名...
本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
**Floyd算法详解** Floyd算法,又称为Floyd-Warshall算法,是解决图论中最短路径问题的一种经典算法。该算法的核心思想是通过动态规划的方法,逐步更新图中所有节点之间的最短路径,最终得到任意两个节点间的最短...
### Floyd算法求点与点之间的最短路径 #### 背景介绍 在图论中,寻找两点间最短路径的问题十分常见。特别是在处理复杂的网络结构时,如何快速找到两个节点间的最短路径成为了关键所在。针对这类问题,通常有两种...
**Floyd算法**,也称为Floyd-Warshall算法,是一种经典的图论算法,主要用于解决多点间的最短路径问题。在数学建模中,它是一个极其重要的工具,能够找到图中所有节点对之间的最短路径。这个算法的核心思想是通过...
基于Floyd算法的无人驾驶汽车路径规划模型是利用图论中的经典算法Floyd算法来解决无人驾驶汽车在复杂道路环境中寻找最优路径的问题。Floyd算法由罗伯特·弗洛伊德(Robert W. Floyd)提出,主要目的是解决带权有向图...
《Floyd算法在配送中心选址的应用》 在物流与供应链管理中,配送中心的选址是一项至关重要的决策。它直接影响到公司的运营成本、服务质量以及客户满意度。在这个过程中,Floyd最短路径算法作为一种高效的图论算法,...
### Floyd算法详解 #### 一、算法介绍与背景 Floyd算法,又称弗洛伊德算法,是一种在图论中非常重要的算法。该算法能够高效地解决加权图中的所有顶点对之间的最短路径问题(All Pairs Shortest Path Problem, APSP...
**Floyd算法**,也称为Floyd-Warshall算法,是一种在图中寻找所有节点对之间最短路径的算法。这个算法是由Robert Floyd在1962年提出的,主要用于解决有向图或无向图中的最短路径问题。在C++编程语言中实现Floyd算法...
Dijkstra、Floyd算法Matlab,Lingo代码的实现。
Floyd算法,又称为Floyd-Warshall算法,是解决图论中的最短路径问题的一种经典方法。在计算机科学中,特别是在算法设计领域,它被广泛应用于网络路由和行程规划。C语言作为基础的编程语言,是实现这种算法的理想选择...
Floyd算法,也被称为Floyd-Warshall算法,是一种用于解决图中所有顶点对之间的最短路径问题的算法。这个算法是由Robert Floyd在1962年提出的,主要用于求解带权有向图或无向图的最短路径。在C#中实现Floyd算法,我们...