1
我是圖論的新手。 我們從節點（1,1）開始，需要到達節點（r，c），也就是說矩形可以用編號爲2D笛卡爾平面的節點想象出來，我們從左上角的節點開始搜索，右節點。從一個節點到另一個節點的遍歷有一定的權重，那麼可以使用O（n）中的BFS（Breadt First Search）來解決加權圖的最小代價路徑嗎？如果BFS無法實現，您能否提出一些不同的算法。在此之前謝謝。可以使用O（n）中的BFS計算加權圖的最小成本路徑嗎？
A
回答
2
如果你是新手，那麼你應該看看Dijkstra's algorithm這是最知名的算法，應該做你想做的。你可以調整BFS來做到這一點，但它會非常緩慢（可能更像Dijkstra一樣少）。如果您有任何問題，請嘗試並返回
相關問題
- 1. 在R中使用BFS計算最短路徑
- 2. 計算加權最短路徑的未加權長度
- 3. 如何計算BFS算法中的移動？ （在迷宮中的最短路徑）
- 4. 如何使用bfs在未加權圖上實現多源最短路徑？
- 5. 可以在o（n）時間內完成計算冪運算，即計算x n嗎？
- 6. 我可以在圖中使用Dijkstra的最短路徑算法嗎？
- 7. 在ocamlgraph中可以使用Goldberg算法來查找最小成本流圖嗎？
- 8. 使用BFS在圖中查找路徑
- 9. 計算最小的 - 切向加權圖使用
- 10. 我們可以使用BFS（以最優方式）查找加權有向非循環圖中從源節點到所有其他節點的最短路徑嗎？
- 11. 使用BFS找到最短路徑
- 12. 在加權圖中確定最佳路徑的算法
- 13. 通過加權圖的最短路徑
- 14. 加權圖的BFS算法 - 查找最短距離
- 15. 計算最小路徑在SQL表
- 16. 如何使用networkx查找加權圖中的最短路徑？
- 17. 可以用小於n-1的連續乘法計算2^n嗎？
- 18. BFS重建路徑以獲得最短路徑
- 19. 尋找加權無向圖中固定成本的路徑？
- 20. 加權圖的小波計算
- 21. 在C++中使用BFS的最短路徑
- 22. 使用HashMaps和ArrayList的最短路徑（使用BFS）
- 23. O（n）排序算法可能嗎？
- 24. 我可以增加設計中使用的授權令牌的大小嗎？
- 25. 使用Cypher或Gremlin可以通過遍歷成本獲得最短路徑嗎？
- 26. Dijkstra算法計算N條最短路徑
- 27. 使用堆棧查找加權圖的最短路徑
- 28. 如何從Java中的文本文件爲Dijkstra的最短路徑算法生成加權圖的映射？
- 29. 最小路徑算法
- 30. 我可以使用js ajax調用的路徑路徑嗎？
...或者Bellman-Ford算法如果權重可以爲負 – SomeWittyUsername