我正在做一个任务，让我遍历一个简单的正方形图形，目的是积累最少的危险。终点很简单：从左上角顶点到右下角我只能在顶点之间水平和垂直移动地牢中的每个房间（图中的每个顶点）都有指定的危险级别。
例子：
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
我一直在胡思乱想使用优先级队列，但我仍然不知道如何，确切地说，我会首先使用这个p.q.。
我可以尝试Dijkstra的算法，但我不是计算节点之间的距离，而是计算最小化的危险这就是说，我假设一个房间的危险在于两个节点之间边缘的重量，对吗？
我希望有人能给我一个主意，告诉我如何解决这个问题。如果有帮助的话，我会用Python编写这个程序。
最佳答案
我解决这些问题已经有一段时间了，但我很确定这里使用的算法是Dijkstra的
对于图中给定的源节点，算法会找到
该节点与其他节点之间的最短路径也可以使用
用于查找从单个节点到单个节点的最短路径
目标节点通过停止算法一次到达
目标节点已确定…[基于实现
在最小优先级队列上]是渐近已知最快的
任意有向图的单源最短路径算法
具有无限的非负权重。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
你的直觉是正确的，但在这种情况下，你被“距离”的定义绊倒了。与其用危险来思考问题，不如在头脑中简单地把“危险”转换成“距离”。在图的左上角和右下角节点之间找到最小危险路径的问题就变成了在这些节点之间找到最短路径的问题，这正是dijkstra所要解决的问题。
关于python - 图上的最短(和最小危险)路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30181204/