How can I use Dijkstra's algorithm on an adjacency matrix with no costs for edges in Python? It has 1 if there is an edge between 2 vertices and 0 otherwise. The explanations that I've found on the internet are all for graphs with costs.
2
-
5Just assume all edges have cost 1.j_random_hacker– j_random_hacker2015-04-17 12:14:02 +00:00Commented Apr 17, 2015 at 12:14
-
See [Calcuating the shortest path between any two vertices u,v in G][1]. [1]: stackoverflow.com/questions/29512280/…Qriss– Qriss2015-04-17 12:53:00 +00:00Commented Apr 17, 2015 at 12:53
Add a comment
|
3 Answers
Dijkstra's algorithm requires edge cost to work. If you want to run the algorithm on a graph with "no costs", I'll assume that you're trying to find the shortest path between 2 vertices in terms of number of edges in the path.
In that case, you can just assume that every edge has cost 1, and Dijkstra's algorithm will work as intended. Make also sure that you ignore non-existing edges in your search (you don't want the zeroes in the matrix to be counted as zero-cost edges).
Comments
When I had to implement Dijkstra's algorithm in php to find the shorter way between 2 tables of a database, I constructed the matrix with 3 values : 0 if the 2 points are the same, 1 if they are linked by an edge, -1 otherwise.
After that the algorithm just worked as intended.
