找到间接列车连接

Question

我必须在两个给定的城市代码之间找到火车旅程,如果没有直接路线,那么我应该通过其他旅程找到间接路线.如果我想从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
}

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

Answer 1

你有什么,是一个图表.

有很多方法可以找到一个路径,许多人找到最短路径和多找到最便宜的路径.

这不是一个简单的其他声明,但我建议你阅读这些:

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

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