shortest-path

2熱度

2回答

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

-2熱度

1回答

Java如何告訴我去過一個數組中的所有數字

所以我有一個包含正整數的N大小的數組A. 該陣列可能有許多重複，我想找到最短的距離去旅遊陣列，並訪問陣列中發生的每個數字迭代從A [0]開始的數組的最佳方式是什麼上。到目前爲止，我已經想出了將所有數字添加到一個集合中，以便我可以比較，如果我已經在那裏。例如下面的數組中的最短距離訪問所有數字是5 Integer[] nums = { 2, 6, 7, 2, 3, 3, 1, 2 }; ，所

0熱度

1回答

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

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

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是一個好方法，因爲我不需要遍歷數組

1熱度

1回答

帶BFS的ShortestPath（BreadthFirstSearch）

我想返回圖的兩個頂點之間的最短路徑。我寫了一段代碼來查找breadthFirstSearch，但我不知道如何修改它以使其返回最短路徑。下面是我的廣度FirstSearch函數 private void breadthFirstSearch(T start,T end){ Queue<T> queue = new LinkedList<>(); Set<T> visited =

-1熱度

1回答

確定字典中從x鍵到y鍵的最快路徑？

如何從字典中的關鍵字x到關鍵字y獲得最快的可能方式，假定它們都是通過它們的數組值連接的。 network={ 1: [3], 2: [4], 3: [1, 8, 7, 6, 4], 4: [2, 3, 6, 5], 5: [4, 11, 10], 6: [3, 11, 4], 7: [3, 8, 11], 8: [3, 16, 9, 7], 9: [8, 16, 14, 11],

0熱度

1回答

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

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

0熱度

2回答

Neo4j最低共同祖先節點未找到

我已經加載了DNA SNP的分層樹（DAG）。我想確定最低的共同祖先。此查詢的工作，產生一個正確的節點： Match (n:SNPNode{SNP:'R-Z11'}), (m:SNPNode{SNP:'R-BY13828'}) match path=(n)-[:SNPParent*..99]->(MRCA)<-[:SNPParent*..99]-(m) return MRCA.SNP 然

0熱度

1回答

如何找到通過至少一個強制節點的兩個節點之間的最短距離？

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