C++ Dijkstra 算法 - 打印边缘 name/type

Question

我目前正在研究 Dijkstra 的最短路径问题。我在这个项目中没有什么特别的，算法是标准的（用一组对实现）除了我需要打印从一个顶点到另一个顶点的边类型。

假设我有 4 个顶点和 5 个边。存在一对顶点 p(v1, v2) 使得有 2 条或更多条边连接 v1 和 v2。例如，我们想要找出从伦敦到巴黎的距离。我们知道我们都可以开车（一种边）或者我们可以买机票（另一种边）。我想做的是打印边的类型。

示例：我有两种方式从伦敦到达巴黎：伦敦 -> 加来 -> 巴黎，最短 5 小时车程；伦敦 -> 巴黎，乘飞机最短 1 小时。

我很清楚，如何打印最短时间或最短距离，如何打印路径等。但是，我如何打印边缘类型（运输类型），例如 'by plane' 或 'by car'?这是我尝试过的：

struct neighbor {

int target_vertex;
double weight;
int type;
// for type: 0 - car
// 1 - bus
// 2 - plane

};

但是，我还是想不通，在计算最短路径时如何存储这些边 'types'。

代码在这里：https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

Answer 1

您已经拥有此信息，它存储在 prev_type[x] 数组中。该数组包含您用来到达最终节点 t 的 transport 的类型。它与记住父节点或您到达当前节点的节点节点的数组 prev[] 结合使用。因此，您从 t（最终节点）开始并调用 prev[t] 以获取其父节点，然后 prev_type[t] 将包含用于到达 t 的传输类型。继续这种方式返回，直到到达 s（开始）节点。

Answer 2

解决了问题，预定义了所有可能的场景，从一个城市到另一个城市（基本上 - 所有城市的组合）。

 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 ";
        }
    }

from = 起始城市。

to = 我们要去的目的地。

我确信该解决方案不是最好的解决方案，但对于这种具有少量节点和边的特定情况，它是适用的。

C++ Dijkstra 算法 - 打印边缘 name/type

C++ Dijkstra Algorithm - print edge name/type

c++

algorithm

graph

dijkstra