python - Shortest (and Least Dangerous) Path on a Graph -

i working on assignment has me traversing simple, square graph goal of accumulating least amount of danger. end points simple: top left vertex bottom right. restricted moving horizontally , vertically between vertexes. each room in dungeon (each vertex on graph) has specified danger level.

example:

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 

i have been throwing around idea of using priority queue, still don't know how, exactly, use p.q. in first place.

i try dijkstra's algorithm, not calculating distance between nodes; rather, calculating minimized danger. being said, right assume danger in 1 room weight on edge between 2 nodes?

i hoping give me idea how approach problem. writing program in python if help.

it's been while since these problems, pretty sure algorithm use here dijkstra's. wikipedia:

for given source node in graph, algorithm finds shortest path between node , every other. can used finding shortest paths single node single destination node stopping algorithm once shortest path destination node has been determined... [the implementation based on min-priority queue] asymptotically fastest known single-source shortest-path algorithm arbitrary directed graphs unbounded non-negative weights.

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

your intuition correct, tripped definition of "distance" in case. instead of thinking of problem in terms of danger, convert "danger" "distance" in mind. problem of finding least dangerous path between top-left , bottom-right nodes of graphs becomes finding shortest path between nodes, precisely dijkstra's supposed solve.