查找間接火車連接

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

你在那裏，是一個圖。

有很多方法可以找到一個路徑，許多人發現最短路徑和許多找到最廉價路徑。

這不是一個簡單的else語句，但我建議你讀了這些：

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

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

Answer 2

我建議你閱讀下面的短文（這是很短）：

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

它由Guido von Rossum撰寫， Python編程語言的創建者。

我喜歡它，因爲它討論瞭如何使用字典（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 

注意，它是一個遞歸實現。

Answer 3

您可以看看Google在Google地圖中爲Google Transit做了些什麼：http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf。