Dijkstra的三座標

算法 - 頂點我經歷的Dijkstra最短路徑算法去了，而我在練習我遇到了一個問題，在頂點不是單號（比如1,2,3 ...和所以），但它是一對更具體地給予作爲（x，y）座標。我從來沒有做過這樣的問題，我也沒有見過他們。請你幫我解決這樣的問題。 O（V^2）熱烈歡迎Dijkstra的三座標

來源

2015-04-27 chota bheem

使用散列圖將座標映射到整數頂點。現在你有一個節點爲單個數字的圖。應用dijkstra的算法。

時間複雜度：O(V)用於轉換爲整數頂點。
O(V^2)運行dijkstra的算法。
因此總體複雜度爲O(V^2)。

僞代碼：

int cntr = 0; 
for(Edge e : graph){ 
    int from = e.from; 
    int to= e.to; 
    if(!map.contains(from)){ 
     map.put(from, cntr++);  
    } 

    if(!map.contains(to)){ 
     map.put(to, cntr++);  
    } 
}

來源

2015-04-27 16:37:39

我明白了，你的意思是類似於map ，int> mp;但是，我應該爲每個鍵分配什麼樣的價值？我的意思是它必須是獨一無二的，我該怎麼做？ –

只需增加一個計數器並將其分配給節點即可。 @chotabheem看到編輯。 –

這真是太好了:)謝謝！ –

每個頂點還是會有一個id（你可以分配，如果不提供）。笛卡爾座標只是頂點的附加屬性，可用於計算連接頂點之間的距離。（sqrt（delta_x^2 + delta_y^2））

來源

2015-04-27 16:38:25

Dijkstra的三座標

回答

相關問題