2

我必须找到两个给定城市代码之间的火车旅程，如果没有直接路线，那么我应该通过其他旅程找到间接路线。如果我想从 A 到 B，我可能必须从 A 到 C 到 B。

我的火车路线文件格式为：出发代码目的地代码公司价格时间这查看两个城市代码之间的直接路线。

现在我已经将以下循环用于直接连接，并且它有效，我只需要间接连接的帮助。

// load file data into v1

string dep, dest;
cout << "\n\tEnter the departure: ";
cin >> dep;
cout << "\n\tEnter the destination: ";
cin >> dest;

for(int i = 0; i < v1.size(); ++i) {
    // Departure() and Destination(), return the departure/destination codes
    if (v1[i].Departure() == dep && v1[i].Destination() == dest)
          // here I find all the direct routes
    else
         // indirect routes dealt with here
}

我认为对于间接路线，我必须在其他部分处理它们。但我很难知道我会怎么做，我想我必须看看第一次出发的目的地在哪里，并将它与我给定的目的地相匹配。

4

3 回答 3

5

你有什么，是一个图表。

有很多方法可以找到一条路径，很多方法可以找到最短路径，很多方法可以找到最便宜的路径。

这不是一个简单的 else 语句，但我建议您阅读以下内容：

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://en.wikipedia.org/wiki/Shortest_path_problem

于 2013-05-17T19:51:02.487 回答
2

我建议您阅读以下文章（很短）：

http://www.python.org/doc/essays/graphs.html

它由 Python 编程语言的创建者 Guido von Rossum 编写。

std::map我喜欢它，因为它讨论了如何使用字典（用 C++ 语言中的 , ）来实现图形，并提供了非常简短、有效的find_path、find_all_paths和find_shortest_path. 鉴于它们是用 Python 实现的，将它们翻译成 C++ 很简单（因为 Python 易于阅读；将其视为伪代码而不是Python 解决方案）。

例如，以下代码实现find_all_paths：

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

请注意，它是一个递归实现。

于 2013-05-17T19:58:37.137 回答
1

您可以在 Google 地图中查看 Google 为 Google Transit 所做的工作：http: //ad.informatik.uni-freiburg.de/files/transferpatterns.pdf。

于 2013-05-17T20:04:23.707 回答