CODEWITHSUNDEEP
pythonalgorithm
user4064253
user4064253

Reputation:

Shortest (and Least Dangerous) Path on a Graph

I am working on an assignment that has me traversing a simple, square graph with the goal of accumulating the least amount of danger. The end points are simple: from the top left vertex to the bottom right. I am restricted to moving horizontally and vertically between vertexes. Each room in the dungeon (each vertex on the graph) has a 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 the idea of using a Priority Queue, but I still don't know how, exactly, I would use that P.Q. in the first place.

I could try Dijkstra's Algorithm, but I am not calculating distance between nodes; rather, I am calculating minimized danger. That being said, am I right to assume that the danger in one room is the weight on the edge between two nodes?

I was hoping someone could give me an idea as to how I could approach this problem. I will be writing the program in Python if that is any help.

Upvotes: 1

Views: 419

Answers (2)

rino
rino

Reputation: 1

When using Dijkstra's algorithm here, if the goal is not only to print total danger but also route how to reach the destination with least danger on the way, you can either store full route for every reached node (if space is not a concern), or store previous node and then go backwards once finish is reached (preferred solution).

Also, in case you need to print all routes with minimum danger, it is a whole different story.

Upvotes: 0

oxymor0n
oxymor0n

Reputation: 1097

It's been a while since I do these problems, but I am pretty sure the algorithm to use here is Dijkstra's. From Wikipedia:

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

Your intuition is correct, but you were tripped up by the definition of "distance" in this case. Instead of thinking of the problem in terms of danger, simply convert "danger" to "distance" in your mind. The problem of finding the least dangerous path between the top-left and bottom-right nodes of the graphs then becomes finding the shortest path between those nodes, which is precisely what Dijkstra's is supposed to solve.

Upvotes: 1

Related Questions