首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >C++ Dijkstra算法-打印边缘名称/类型

问C++ Dijkstra算法-打印边缘名称/类型
EN

Stack Overflow用户
提问于 2016-11-30 20:38:02
回答 2查看 388关注 0票数 0

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

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

从伦敦到巴黎有两条路:伦敦-> Paris,最短时间5小时,乘汽车;伦敦->巴黎,最短时间1小时,乘飞机。

我很清楚,如何打印最小的时间或最小的距离,如何打印路径等。但是,如何打印“乘飞机”或“乘车”之类的边缘类型(交通类型)?以下是我尝试过的:

代码语言:javascript
复制
struct neighbor {

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

};

但是,我还是想不出,在计算最短路径的同时,我该如何存储这些边缘类型。

代码:https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-12-09 20:02:02

解决了这个问题,预先定义了所有可能的scenarious,从一个城市到另一个城市(基本上-所有城市的组合)。

代码语言:javascript
复制
 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 ";
        }
    }

从开始的城市

我们要去的目的地。

我相信这个解决方案并不是最好的,但是对于这个节点和边数较少的特殊情况,它是适用的。

票数 0
EN

Stack Overflow用户

发布于 2016-11-30 20:42:36

您已经有了这个信息,它存储在prev_type[x]数组中。此数组包含用于到达最终节点transport的类型t。它与记住父节点的数组prev[]或到达当前节点的节点结合工作。因此,您从您的t (最终节点)开始,调用prev[t],以获取它的父节点,而prev_type[t]将包含用于到达t的传输类型。继续以这种方式返回,直到到达s (开始)节点为止。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40897735

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档