dijkstra

0熱度

1回答

我有一個具有約5000個節點的雙向加權圖表我有一個「重要」節點（100左右）列表。給定一個起始節點和一個結束節點，如何找到這兩個節點之間的最短距離，這兩個節點至少通過一個「重要」節點。請注意，沒有負面的邊緣。我實現了dijkstra的算法來找到給定兩個節點的最短距離。我知道如何解決這個問題的唯一方法是查看重要節點列表，找到所有重要節點從開始 - >重要節點＃1 - >結束的距離，然後取最小值。有

0熱度

1回答

任何人都可以描述Dijkstra算法的這部分代碼

我不明白Dijkstra算法的這個給定的部分。我想逐行理解這部分代碼。代碼： bool operator < (const DATA &p) const { return p.dist > dist; } 我的C/C++代碼的基本知識。

2熱度

2回答

Python的廣度優先於谷歌FOO條（準備兔子逃脫）

我工作了下面的問題，我認爲我有它主要是解決最短路徑，但是一些測試用例執行失敗：你有空間站的部分地圖，每個從監獄出口開始，並在逃生艙的門口結束。該地圖以0和1的矩陣表示爲，其中0是可通過的空間並且1是不通過的牆壁。監獄外的門位於左上方（0,0），進入逃生艙的門位於右下角（w-1，h-1）。編寫一個函數答案（地圖），它可以生成從監獄門到逃生吊艙的最短路徑長度，您可以在此處移除一堵牆作爲重建計

0熱度

3回答

如果2個圖節點之間的間接路徑比直接路徑短，Dijkstras算法能檢測到它嗎？

Dijkstras算法假設基於起始節點和中間節點之間的邊權重的最近鄰居。重複此操作直到到達目的地節點。如果啓動節點和中間節點之間的最短路徑是通過其他幾個中間節點的間接路由，該怎麼辦？

0熱度

1回答

修改Dijkstra以保存具有相同值的路徑 - StackOverflow錯誤

我試圖修改Dijkstra的算法以顯示所有具有最小值的路徑。所以我決定使用以前的頂點列表。我添加了一個if子句，用於檢查路徑是否爲具有最小值的前一個值，並將前一個頂點添加爲當前父元素的父元素。問題是我得到一個StackOverflow錯誤，我不知道是什麼導致它。這是我的代碼：下面的代碼的目的是爲圖中的所有頂點計算Dijkstra，計算頂點出現在最小路徑中的次數，並按降序顯示它們全部。 pub

0熱度

1回答

有人可以檢測到在這段代碼中使用python實現dijkstra算法的錯誤嗎？

我想實現dijkstra的算法（在無向圖上）找到最短路徑，我的代碼是這樣的。注意：我沒有使用堆/優先級隊列或任何東西，但鄰接列表，字典存儲權重和布爾表，以避免在循環/遞歸循環永遠。此外，該算法適用於大多數的測試案例，但未能爲這個特殊的位置：https://ideone.com/iBAT0q 重要：圖形可以從V1到V2（反之亦然），你必須使用最小重量有多個邊緣。 import sys sys.

1熱度

1回答

製作Dijkstra算法賬戶回程時間

這樣的問題去如下：未加權樹提供給我，讓我可以在任一節點，即時通訊預計參觀的是香港專業教育學院在陣列中提供了只有特定的節點啓動。我的目標是找出需要花費的時間來到每個節點。每條邊都需要一分鐘才能通過。我已經嘗試實現Dijkstra算法，以便開始在我想參觀，並試圖從那裏形成的最短路徑的節點。但我的問題是，雖然提供了一個解決方案，但它可能不是最有效的解決方案，因爲我不知道如何強制Dijkstra算法來

1熱度

1回答

我正在嘗試實現類Dijkstra的算法

我應該得到0-3-6-5作爲成本的輸出。 -1-0-3-1用於前一個數組的輸出。和1-1-1-1爲訪問數組。我得到了0-3-7-5爲我的輸出成本和-1-0-1-1爲以前。如果可以的話請幫忙。我試圖看看7是什麼時候它應該是一個六，而我沒有搞清楚。這是我第一次用C語言進行編碼，因此看起來有點草率。 #include <stdlib.h> #include <stdio.h> #include

0熱度

1回答

以最少的跳數穿越陣列，面向科技公司面試的在線編碼挑戰

我做了一個面試問題/編碼挑戰，我需要通過數組「arr」提出最短的「跳數」，其中每個我可以跳轉1-> arr [i]。一個難題就是我不能登陸任何以0爲值的索引。當我開始研究這個問題時，我開始將數組作爲一個有向圖，其中每個索引都是節點i，並且他們的子節點由所有可到達節點i + 1-> i + arr [i]表示。當你想象這是一個圖，我認爲使用Dijkstra's是一個好方法，因爲我不需要遍歷數組

0熱度

1回答

使用Dijkstra's將2的冪返回相同的最短路徑嗎？

我有一個圖G =（V，E），其中有兩個權重函數w1（e）和w2（e），其中 w1（e）=（w2（e））^ 2。所有邊緣權重都是獨一無二的。在兩個權重函數下，Kruskal的算法將返回相同的最小生成樹。我知道kruskal是貪婪的，會選擇最短/最低成本的路徑。既然它們是肯定的，只要沒有成本爲1.5或者更低的路徑，我們最終會選擇相同的MST。在兩個權重函數下，Dijkstra的算法將返回相同的