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 and finding the shortest path using a given source and destination vertex.
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
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 , source vertex, and destination vertex.
find_path(G, Source, Destination)
If you need to add an edge in the graph between vertices and with weight , 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.
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=[3], costs=[3], total_cost=3)
Which is the path from nodes 1 and 7 with a cost of 3.