Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

What is the Dijkstar library in python?

Muhammad Muzammil

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Description

The Dijkstar library in Python contains abstractions for the famous Dijkstra’s single-source shortest path algorithm.

This library includes the functionality for adding vertices and (either weighted or non-weighted) edges to a graph GG and finding the shortest path using a given source and destination vertex.

Install and import

In Linux, the Dijkstar library can be installed by typing the following command in the terminal:


$ pip install Dijkstar

And can be imported in a python file using:


from dijkstar import Graph, find_path

Useful functionalities

The Graph object contains the necessary architecture for building a Graph (vertices, edges, weights).

Moreover, the find_path() function will perform the underlying Dijkstar’s algorithm under the hood when provided with Graph GG, source vertex, and destination vertex.


find_path(G, Source, Destination)

If you need to add an edge in the graph between vertices aa and bb with weight ww, you may use the add_edge() function.


add_edge(a, b, w)

Since the graph used by the Dijkstar library is in the form of a python dictionary, the .json files can be leveraged to transfer graphs to and from different python files.

Code

The python file below displays how to use the Dijkstar library:

from dijkstra import Graph, find_path
graph = Graph ()
graph.add_edge(1, 3, 2)
graph.add_edge(3, 4, 4)
graph.add_edge(4, 6, 10)
graph.add_edge(4, 7, 1)
graph.add_edge(1, 7, 3)
shortest_path = find_path(graph, 1, 7)
print(graph)
print(shortest_path)

This program outputs the path:

PathInfo(nodes=[1, 7], edges=[3], costs=[3], total_cost=3)

Which is the path from nodes 1 and 7 with a cost of 3.

RELATED TAGS

python
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring