URL的最短路徑算法

我在找到兩個URL之間的最短路徑時遇到了問題。我們提供的.csv列出了一串用逗號分隔的網站。每個網站都可以訪問該頁面超鏈接中的下一個網站。例如，如果該文件讀取espn.com，espn.com/nba，espn.com/nbaschedules，則可以從espn.com轉到nba頁面，並從nba頁面轉到nba日程表。我的工作是找到從一個網站到另一個網站的最少點擊次數。這是我迄今爲止如何存儲文件。我正在使用的是用於存儲的STL unordered_map。URL的最短路徑算法

ifstream inFile; 
ofstream outFile; 
inFile.open("urls.csv"); 
string line; 
unordered_map<string, vector<string>> urlAdjList; 
while(getline(inFile, line)) //Reads each line one at a time. 
{ 
    int firstWord = 0; 
    istringstream iss(line); 
    string firstURL, url; 
    while(iss >> url) 
    { 
     if(firstWord == 0 && url != "|") 
     { 
      firstURL = url; 
      urlAdjList[firstURL]; 
      firstWord = 1; 
       outFile << firstURL << endl; 
     } 
     else 
      urlAdjList[firstURL].push_back(url); 
    } 
} 
//Find the shortest path between mURL and nURL?

我的問題是我把它存儲正確嗎？我需要使用Dijkstra算法還是廣度優先搜索？

來源

2014-07-23 user3485650

您可能需要爲此使用Dijkstra算法。您還需要以某種圖形結構存儲所有數據，例如。

struct graph_node { 
    vector<graph_node*> neighbours; 
    string url; 
}

您也可以使用地圖來存儲所有的value-> graph_node指針。然後使用Dijkstra的算法在建立圖形後找到最短路徑。

來源

2014-07-23 02:00:59

只有在超鏈接之間切換的代價不同時，Dijkstra的算法纔有效。

所以比較喜歡BFS。

O（V）是爲O更好（（V + E）的日誌（V + E））{V-頂點，E-邊緣}

最好是曲線圖存儲在ID的鄰接表使用矢量<矢量< int>>而不是將其存儲在矢量<矢量<字符串>>。使用數組來標識一個id的URL。

來源

2014-07-23 04:52:22 cegprakash

URL的最短路徑算法

回答

相關問題