We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I used Dijkstra's Algorithm (using heapq (similar to priority queue) of Python), graph is such that there is a source vertex and n^2 other vertices. Edges from source vertex to the vertices of the first column are having weight = grid(i,0) for i=0 to n-1 and all other vertices (i,j) have incoming edges (from left to right, up to down, down to up) with weight=grid(i,j). Then take the minimum dist(i,n-1) for i=0 to n-1.
Works fine in Python 3 but avoid creating a "Graph". Use list not dictionary. dict is very slow. Only for source, adjacent vertices have a condition, for all other vertices, the conditions are same so it can be solved without actually building a graph with adjacency lists and costs.
Even Dijkstra's Algorithm worked in O(n^2) by just adding one extra vertex.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #82: Path sum: three ways
You are viewing a single comment's thread. Return to all comments →
I used Dijkstra's Algorithm (using heapq (similar to priority queue) of Python), graph is such that there is a source vertex and n^2 other vertices. Edges from source vertex to the vertices of the first column are having weight = grid(i,0) for i=0 to n-1 and all other vertices (i,j) have incoming edges (from left to right, up to down, down to up) with weight=grid(i,j). Then take the minimum dist(i,n-1) for i=0 to n-1.
Works fine in Python 3 but avoid creating a "Graph". Use list not dictionary. dict is very slow. Only for source, adjacent vertices have a condition, for all other vertices, the conditions are same so it can be solved without actually building a graph with adjacency lists and costs.
Even Dijkstra's Algorithm worked in O(n^2) by just adding one extra vertex.