Skip to main content
Join the official 2020 Python Developers SurveyStart the survey!

dijkstra is a native Python implementation of famous Dijkstra's shortest path algorithm. The implemented algorithm can be used to analyze reasonably large networks. The primary goal in design is the clarity of the program code. Thus, program code tends to be more educational than effective.

Project description

Dijkstra

Python CI Coverate Status

example1

Package author: Jukka Aho (@ahojukka5, ahojukka5@gmail.com)

dijkstra is a native Python implementation of famous Dijkstra's shortest path algorithm. The implemented algorithm can be used to analyze reasonably large networks. The primary goal in design is the clarity of the program code. Thus, program code tends to be more educational than effective.

Project source code is licensed undet MIT license. The source code of the project is hosted on on GitHub: https://github.com/ahojukka5/dijkstra. Releases of this package are hosted in PyPi, where they can be easily accessed using pip: https://pypi.org/project/dijkstra/.

Installing package

To install the most recent package from Python Package Index (PyPi), use git:

pip install dijkstra

To install the development version, you can install the package directly from the GitHub:

pip install git+git://github.com/ahojukka5/dijkstra.git

Usage

Package implements two classes, DijkstraSPF and Graph. The above example can be solved with the following code:

S, T, A, B, C, D, E, F, G = nodes = list("STABCDEFG")

graph = Graph()
graph.add_edge(S, A, 4)
graph.add_edge(S, B, 3)
graph.add_edge(S, D, 7)
graph.add_edge(A, C, 1)
graph.add_edge(B, S, 3)
graph.add_edge(B, D, 4)
graph.add_edge(C, E, 1)
graph.add_edge(C, D, 3)
graph.add_edge(D, E, 1)
graph.add_edge(D, T, 3)
graph.add_edge(D, F, 5)
graph.add_edge(E, G, 2)
graph.add_edge(G, E, 2)
graph.add_edge(G, T, 3)
graph.add_edge(T, F, 5)

dijkstra = DijkstraSPF(graph, S)

After running an algorithm, the shortest distance to each node, starting from S, is available:

print("%-5s %-5s" % ("label", "distance"))
for u in nodes:
    print("%-5s %8d" % (u, dijkstra.get_distance(u)))
label distance
S            0
T           10
A            4
B            3
C            5
D            7
E            6
F           12
G            8

Also, we can extract the path. From S to T, the path is:

print(" -> ".join(dijkstra.get_path(T)))
S -> D -> T

It's not mandatory to use Graph. To use your own data structure for graph, you need to subclass AbstractDijkstraSPF and implement two functions connecting graph object to the shortest path finder algorithms: get_adjacent_nodes and get_edge_weight. For example, implementation of DijkstraSPF using Graph is the following:

class DijkstraSPF(AbstractDijkstraSPF):

    @staticmethod
    def get_adjacent_nodes(G, u):
        return G.get_adjacent_nodes(u)

    @staticmethod
    def get_edge_weight(G, u, v):
        return G.get_edge_weight(u, v)

References

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for dijkstra, version 0.2.1
Filename, size File type Python version Upload date Hashes
Filename, size dijkstra-0.2.1-py3-none-any.whl (5.5 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size dijkstra-0.2.1.tar.gz (4.7 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page