How do I do this?

I’ll keep it short. How can I apply Dijkstra’s Shortest Path Algorithm to a grid without explicitly creating a graph such as by using adjacency list or adjacency matrix?

It’s not possible. Can you link the Question?

Case 1 : unweighted edges
distance from (x_1, y_1) to (x_2, y_2) =|x_2-x_1| + |y_2-y_1|

Case 2 : Weighted edges
You’ll need the adjacency list to store the distances.

Here is the problem link https://www.spoj.com/problems/MICEMAZE/

You need to create the adjacency list for this problem. The edges given are random and weighted.

1 Like