CODEWITHSUNDEEP
pythonalgorithmdictionarygraph-algorithmdijkstra
Ahmed Al-haddad
Ahmed Al-haddad

Reputation: 833

How to start Dijkstra's algorithm on a graph stored in a dictionary

I want to implement Dijkstra's shortest-path algorithm, and I'm using a multi-level dictionary to represent my graph. For example:

g = {'A': {'C': 2}, 'B': {'B': 4, 'A': 2}}

I know how to access the inner dictionary using double for loops. But if the user inputs a starting point and an ending point, I face a problem searching for my starting point inside the dictionary using this for loop:

start = input("Starting point : ")
for start in g:
    print start

This will instead print the the keys inside and it will always start from the first key and go through the graph. That's the opposite of what the algorithm says, which is to compare the source point with all the other nodes, and then the point after based on the weight with all the other nodes, and so on.

Can you suggest a way to go about this? How can I start from node B instead of A for example instead of starting from the first key?

Also, do you recommend this dictionary method or is there a better way to it?

Upvotes: 1

Views: 2539

Answers (3)

VHarisop
VHarisop

Reputation: 2826

This piece of code:

for start in g:
    print start

has the variable start iterate over every key of your dictionary. If you wanted to print the value/subdictionary that corresponds to your starting point in the dictionary, just use

print g[start]

As for the algorithn itself, Diego Allen's advice is right.

Upvotes: 1

Diego Allen
Diego Allen

Reputation: 4653

The starting node should be a parameter of your dijkstra function. The function signature should be something like def dijkstra(graph, start):.

To iterate over the connected nodes, I'd use:

for node, cost in graph[start].items():
    print node, cost

Also in dijkstra you should have a data structure to hold the nodes not yet explored decreasingly ordered by cost. Usually a priority queue is used.

Here's a tip: The main loop inside the dijkstra function won't be a for loop, but a while loop checking there's still nodes to explore.

Upvotes: 3

Michael Laszlo
Michael Laszlo

Reputation: 12239

Dijkstra's algorithm solves the single-source shortest-path problem. Given a graph and a vertex in the graph, it finds the shortest path to every other vertex.

If you want your implementation to run fast, you must use a priority queue. It's fine to use a dictionary to represent the graph initially, but you'll want to extract the edges and insert them into the priority queue. Recall that in each iteration of Dijkstra's algorithm, you must pick the cheapest edge among all the edges that cross the frontier between the unexplored part of the graph and the part you've already explored. With a min-cost priority queue, you can pop the cheapest edge off the queue in each iteration.

A simple and efficient implementation of a priority queue is a heap. I recommend that you either use Python's built-in heap queue or implement your own min-heap with a list.

Upvotes: 2

Related Questions