Find the shortest path length in the matrix. Is Dijkstra not optimal for this case?
I'm trying to solve the following problem from a project euler (see description and example in link, but here's a short explanation).
in the matrix, find the minimum sum of the path from top-left to bottom-right by moving left, right, up and down
Right after I looked at the problem, the obvious solution that came to my mind is to create a graph from a matrix and then use Dijkstra to find the shortest path.
To build a graph from a matrix N*M
, for each element, (i, j)
I create a vertex i * N + j
and connect it to any other vertex (which can be connected using UP, RIGHT, DOWN, LEFT), and the edge will be the value of the element with which I connect in the matrix. After that, I create two other vertices -1
, linked to 0
and -2
linked to N*M - 1
, which will be my start and end vertices (both connections have 0 cost).
After that I do Dijkstra to find the shortest path cost from -1
to -2
. My Dijkstra implementation uses a priority queue and looks like this:
func dijkstraCost(graph map[int]map[int]int, start, end int) int{
if start == end{
return 0
}
frontier := make(PriorityQueue, 1)
frontier[0] = &Item{value: start, priority: 0, index: 0}
visited := map[int]bool{}
heap.Init(&frontier)
for frontier.Len() > 0 {
element := heap.Pop(&frontier).(*Item)
vertex, cost := element.value, element.priority
visited[vertex] = true
neighbors := graph[vertex]
for vertex_new, cost_new := range(neighbors){
if !visited[vertex_new]{
if vertex_new == end{
return cost + cost_new
}
heap.Push(&frontier, &Item{
value: vertex_new,
priority: cost + cost_new,
})
}
}
}
return -1
}
where the implementation of the priority queue is taken from the heap container (example PriorityQueue) with one minor modification:
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].priority > pq[j].priority // changed to <
}
The graph that I provide to the function looks like this:
map[13:map[8:965 18:121 12:746 14:111] 16:map[11:803 21:732 15:537 17:497] 3:map[8:965 2:234 4:18] 4:map[9:150 3:103] 22:map[17:497 21:732 23:37] -1:map[0:131] 17:map[16:699 18:121 12:746 22:524] 1:map[6:96 0:131 2:234] 9:map[4:18 14:111 8:965] 11:map[6:96 16:699 10:630 12:746] 19:map[14:111 24:331 18:121] 24:map[23:37 -2:0 19:956] 2:map[3:103 7:342 1:673] 15:map[10:630 20:805 16:699] 18:map[13:422 23:37 17:497 19:956] 10:map[5:201 15:537 11:803] 14:map[19:956 13:422 9:150] 0:map[5:201 1:673] 6:map[5:201 7:342 1:673 11:803] 8:map[9:150 3:103 13:422 7:342] -2:map[] 12:map[7:342 17:497 11:803 13:422] 20:map[15:537 21:732] 21:map[16:699 20:805 22:524] 5:map[0:131 10:630 6:96] 23:map[18:121 22:524 24:331] 7:map[2:234 12:746 6:96 8:965]]
It works correctly, but the problem is that it is considered ineffective (judging by the Hackerrank version of the problem ). It should work by finding the value of the best solution for the 700x700
matrix in less than 4 seconds, whereas my solution takes 10 seconds.
I thought I was doing something wrong in go, so I repeated the same solution in python (where it took about 70 seconds for a 700x700 matrix)
My question: I am using the correct approach to find the best solution in the matrix. If so, what am I doing wrong with my implementation?
PS I have a complete go and python solution, just thought the question was too long even without them.
source to share
Dijkstra has to go through, I am just doing the view with JAVA and it took less than a second to complete each task.
As I mentioned, each value in the matrix can go up to 10 ^ 9, your solution may face a number overflow problem, which may affect the running time.
My code:
<!-- language:java -->
static int[]X = {0,1,0,-1};
static int[]Y = {1,0,-1,0};
public static void main(String[] args) throws FileNotFoundException {
// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
// "output.txt")));
PrintWriter out = new PrintWriter(System.out);
Scanner in = new Scanner();
int n = in.nextInt();
long[][]map = new long[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = in.nextLong();
}
}
PriorityQueue<Pos> q= new PriorityQueue();
long[][]dist = new long[n][n];
for(long[]a : dist){
Arrays.fill(a,Long.MAX_VALUE);
}
q.add(new Pos(0,0,map[0][0]));
dist[0][0] = map[0][0];
while(!q.isEmpty()){
Pos p = q.poll();
if(dist[p.x][p.y] == p.cost){
for(int i = 0; i < 4; i++){
int x = p.x + X[i];
int y = p.y + Y[i];
if(x >= 0 && y >= 0 && x < n && y < n && dist[x][y] > dist[p.x][p.y] + map[x][y] ){
dist[x][y] = dist[p.x][p.y] + map[x][y];
q.add(new Pos(x,y,dist[x][y]));
}
}
}
}
out.println(dist[n - 1][n - 1]);
out.close();
}
static class Pos implements Comparable<Pos>{
int x, y;
long cost;
public Pos(int x, int y, long cost) {
super();
this.x = x;
this.y = y;
this.cost = cost;
}
@Override
public int compareTo(Pos o) {
// TODO Auto-generated method stub
return Long.compare(cost, o.cost );
}
}
Update
I think your Dijkstra implementation is wrong:
for frontier.Len() > 0 {
element := heap.Pop(&frontier).(*Item)
vertex, cost := element.value, element.priority
//You didn't check for visited vertex here!
visited[vertex] = true
neighbors := graph[vertex]
for vertex_new, cost_new := range(neighbors){
if !visited[vertex_new]{//You can add same vertex multiple times here!
if vertex_new == end{
return cost + cost_new
}
heap.Push(&frontier, &Item{
value: vertex_new,
priority: cost + cost_new,
})
}
}
}
In your implementation, you are only updating visited
when a vertex is popping out of the heap, so one vertex can be added and processed multiple times, so it will increase your time complexity significantly.
To fix it
for frontier.Len() > 0 {
element := heap.Pop(&frontier).(*Item)
vertex, cost := element.value, element.priority
if !visited[vertex]{
visited[vertex] = true
neighbors := graph[vertex]
for vertex_new, cost_new := range(neighbors){
if !visited[vertex_new]{
if vertex_new == end{
return cost + cost_new
}
heap.Push(&frontier, &Item{
value: vertex_new,
priority: cost + cost_new,
})
}
}
}
source to share