我目前正在研究Dijkstra的最短路径问题。在这个项目中我没有什么特别的,算法是标准的(用一组对来实现),但我需要打印从一个顶点到另一个顶点的边缘类型。
假设我有4个顶点和5个边。存在一对顶点p( v1,v2),使得v1和v2之间存在两个或多个边。例如,我们想找到从伦敦到巴黎的距离。我们都知道,我们都可以开车(一种边缘)或我们可以买机票(另一种边缘)。我想要做的是打印边缘的类型。
从伦敦到巴黎有两条路:伦敦-> Paris,最短时间5小时,乘汽车;伦敦->巴黎,最短时间1小时,乘飞机。
我很清楚,如何打印最小的时间或最小的距离,如何打印路径等。但是,如何打印“乘飞机”或“乘车”之类的边缘类型(交通类型)?以下是我尝试过的:
struct neighbor {
int target_vertex;
double weight;
int type;
// for type: 0 - car
// 1 - bus
// 2 - plane
};但是,我还是想不出,在计算最短路径的同时,我该如何存储这些边缘类型。
代码:https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d
发布于 2016-12-09 20:02:02
解决了这个问题,预先定义了所有可能的scenarious,从一个城市到另一个城市(基本上-所有城市的组合)。
if (choice == 1) {
switch (from) {
case 0: {
if (to == 1) std::cout << " by foot ";
if (to == 2) std::cout << " by foot -> by bus ";
if (to == 3) std::cout << " by air ";
break;
}
case 1: {
if (to == 0) std::cout << " by foot ";
if (to == 2) std::cout << " by bus ";
if (to == 3) std::cout << " by bus -> by car ";
break;
}
case 2: {
if (to == 0) std::cout << " by bus -> by foot ";
if (to == 1) std::cout << " by bus ";
if (to == 3) std::cout << " by car ";
break;
}
case 3: {
if (to == 1) std::cout << " by car -> by bus ";
if (to == 2) std::cout << " by car ";
if (to == 0) std::cout << " by air ";
}
}从开始的城市
我们要去的目的地。
我相信这个解决方案并不是最好的,但是对于这个节点和边数较少的特殊情况,它是适用的。
发布于 2016-11-30 20:42:36
您已经有了这个信息,它存储在prev_type[x]数组中。此数组包含用于到达最终节点transport的类型t。它与记住父节点的数组prev[]或到达当前节点的节点结合工作。因此,您从您的t (最终节点)开始,调用prev[t],以获取它的父节点,而prev_type[t]将包含用于到达t的传输类型。继续以这种方式返回,直到到达s (开始)节点为止。
https://stackoverflow.com/questions/40897735
复制相似问题