“弗洛伊德-沃尔”算法“和”Dijkstra的算法“”之间有什么区别,哪种算法是图中最短路径的最佳选择?
我需要计算网络中所有对之间的最短路径,并将结果保存到一个数组中,如下所示:
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
我需要知道什么是最理想的旅行路径,每个人同时(假设4个小时)。这些人同时从A市开始(*见表)。
我有三个mysql表,如下所示:
表
people:
id name
1 People A
2 People B
3 People C
city:
id name
1 City A
2 City B
3 City C
... ...
26 City Z
distance:
fromCity toCity distance (km) time (appox. travel in minutes)
1 2
所以我来到了这个美丽的问题,它要求你写一个程序,找出在有向图中是否存在负无穷短路径。(也可以认为是查找图中是否存在“负循环”)。下面是这个问题的链接:
我成功地解决了这个问题,我从图中的任何源开始,运行了两次Bellman Ford算法。第二次运行算法时,我检查节点是否可以松弛。如果是这样,那么在图中肯定有一个负循环。下面是我的C++代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int test;