Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

# What is the Dijkstar library in python?

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 $G$ 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 $G$, source vertex, and destination vertex.

find_path(G, Source, Destination)


If you need to add an edge in the graph between vertices $a$ and $b$ with weight $w$, 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_pathgraph = 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=, costs=, total_cost=3)

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

RELATED TAGS

python
communitycreator

CONTRIBUTOR 