floyd-warshall

11熱度

4回答

我需要找到一個無向圖的最短路徑，其節點是真實的（正和負）加權。這些權重就像您通過輸入節點可以獲得或釋放的資源。路徑的總成本（資源總和）不是很重要，但它必須大於0，且長度必須儘可能短。例如，考慮圖表所示： A-start node; D-end node A(+10)--B(0)--C(-5) \ | / \ |/ D(-5)--E(-5)--F(+10) 的最短路

2熱度

2回答

Floyd-Warshall algorthm如何工作，什麼是K？

我很難理解Floyd-Warshall algorithm。我知道它是如何工作的因爲我知道如何手工完成，但我需要通過計算機瞭解它洞察力。 FOR k <-- 1 TO N DO FOR i <-- 1 TO N DO FOR j <-- TO N DO IF Djk + Dkj < DiJ THEN Dij <-- djk + dkj k

5熱度

2回答

使用Floyd-Warshall尋找所有最短路徑和距離

首先，有一點背景：我正在構建一個帶有基本圖算法（Dijkstra，Floyd-Warshall，Bellman-Ford等）的簡單圖類作爲即將舉行的節目比賽參考表。到目前爲止，我有弗洛伊德，沃肖爾的功能版本，但不足之處是，到目前爲止，它只是讓我在最短的距離值節點兩者之間，不是最短路徑。最好我希望在算法本身中進行路徑建立，而不必調用另一個函數來重建它。下面是關於數據結構的一些信息，我使用的是：

5熱度

1回答

瞭解minimax/maximin路徑（Floyd-Warshall）

我已經實現了Floyd-Warshall算法來解決所有對最短路徑問題。現在我發現我還可以通過簡單的修改來計算極小極大或極大極小的路徑。但我不明白結果是什麼意思（什麼是極大極小路徑）。我在網上發現了一些explanations，但他們讓我感到困惑。 Minimax - 圖問題中的最小最大值包括找到兩個節點之間的路徑，以最小化路徑上的最大成本。 Maximin - Minimax的另一種方式 - 在這

3熱度

1回答

鄰接矩陣/ Floyd/Warshall in lisp

顯然，我的老師認爲即使我們沒有時間學習東西（也沒有足夠的例子），我們應該繼續前進，所以我現在需要知道如何製作Floyd-Warshall和Warshall的算法在clisp中。當我同序言一樣，我的問題是，產生從圖中的鄰接矩陣，在這種情況下，這將是列表的列表，如： ((A B) (A C) (A D) (B C) (C D)) 這應該產生： ((0 1 1 1) (1 0 1 9) (1 1

6熱度

2回答

弗洛伊德 - Warshall算法邏輯 - 卡住

我試圖用這個邏輯來理解正在發生的事情與adjacency matrix，但我massivley困惑的地方說約interspacing是ABCD ..... 任何人都可以解釋這裏發生了什麼？謝謝（標記爲Java作爲其這是在向我們展示的語言，所以如果有人發佈任何代碼示例，他們可以看到它是在語言） http://compprog.wordpress.com/2007/11/15/all-source

0熱度

1回答

Floyd/Warshall算法重建路徑，保存到列表中

兩個簡單的問題和我的大腦不工作。我正在使用Floyd的算法並嘗試重建從頂點U到頂點V的路徑。這裏是我的代碼來重建路徑。例如，令u = 0和v = 3，並且讓從0到3的最短路徑爲0,1,2,3。但是我有兩個問題。我的pathList是類的實例變量：我想列表返回「0,1,2,3」，但它只返回「0,1,2」，或者如果我替換pathList。添加（u）與pathList.add（v），然後它返回只

4熱度

1回答

Floyd/Warshall算法mod找到最大長度最低的路徑k

我在編輯Floyd算法，以代替每個Dk，其中k是最高中間頂點，k是最大路徑長度。最終它將具有與弗洛伊德相同的輸出結果，但每次提煉都可能不同。例如，如果有4個頂點：0,1,2,3，我想從0到3找到最大長度爲K的最便宜的路徑。假定圖被定向。所以如果k = 2，那麼我只能檢查0-> 3 ... 0-> 1-> 3 ... 0-> 2-> 3，其中每個箭頭指示邊/路徑。如果k = 3，那麼我只能檢查0->

1熱度

1回答

Floyd和Warshall在Prolog中的算法

我想在Prolog中編寫這些算法，首先我需要從圖表列表中創建一個矩陣。我之前已經做到了這一點（同時在你們中的一些人的幫助下），但現在我不知道如何將它存儲在列表列表中（我認爲這是prolog最好的方法）。我想我可以從那裏繼續（在每個算法中使用三重for循環）。程序的邏輯對我來說並不困難，但是如何處理數據。對不起，先打擾一下，謝謝！我的矩陣生成： graph(a,b). graph(a,a).

1熱度

1回答

Java：引用圖中的邊線

我正在修改圖形實現以使用Floyd's algorithm來計算所有對最短路徑矩陣。該圖具有相鄰鏈接列表和矩陣實現。現在我正在使用鄰接矩陣，因爲它需要這個算法。 abstract public class GraphMatrix<V,E> extends AbstractStructure<V> implements Graph<V,E>{ /** * Number of vertices i