python - 图上最短(也是最不危险)的路径

Question

我正在完成一项任务，要求我遍历一个简单的方图，目标是累积最少的危险。端点很简单:从左上顶点到右下顶点。我仅限于在顶点之间水平和垂直移动。地牢中的每个房间(图中的每个顶点)都有指定的危险级别。

示例:

0 7 2 5 4    0 -> 1 -> 1 -> 2 -> 2 -> 1 -> 3 -> 1 -> 0
1 5 1 2 1
1 2 2 1 1 
1 9 5 3 5
1 1 9 1 0

我一直在考虑使用优先级队列的想法，但我仍然不知道我将如何使用优先级队列。首先。

我可以尝试 Dijkstra 算法，但我没有计算节点之间的距离；相反，我正在计算最小化的危险。话虽这么说，我是否正确地假设一个房间的危险是两个节点之间边缘的重量？

我希望有人能告诉我如何解决这个问题。如果有帮助，我会用 Python 编写程序。

Answer 1

我已经有一段时间没有做这些问题了，但我很确定这里使用的算法是 Dijkstra 的。来自维基百科:

For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined... [The implementation based on a min-priority queue] is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

您的直觉是正确的，但在这种情况下，您被“距离”的定义误导了。与其从危险的角度思考问题，不如在脑海中将“危险”转化为“距离”。找到图的左上角和右下角节点之间的最不危险路径的问题就变成了找到这些节点之间的最短路径，这正是 Dijkstra 应该解决的问题。