Skip to main content

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

Metadata

Release files for dijkstra 0.2.1

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for dijkstra 0.2.1
File Size Uploaded Provenance Actions
dijkstra-0.2.1.tar.gz 4.7 kB Without provenance Details for dijkstra-0.2.1.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for dijkstra 0.2.1
File Interpreter ABI Platform Actions
dijkstra-0.2.1-py3-none-any.whl Python 3 none any Details for dijkstra-0.2.1-py3-none-any.whl

Total release size: 10.2 kB

Release files / dijkstra-0.2.1.tar.gz

Download URL dijkstra-0.2.1.tar.gz
Size 4.7 kB
Tags Source
SHA-256 checksum
How to use checksums
4773decbba0e999945313f93d1ab523fc9c4c20769b2921330a6b5c137186ccb
BLAKE2b-256 checksum
How to use checksums
b3ad3aaafbf4faca15a850ac7a4ed85b8c7e269f990bd00d66d082616bf5c135
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.46.0 CPython/3.8.2

Release files / dijkstra-0.2.1-py3-none-any.whl

Download URL dijkstra-0.2.1-py3-none-any.whl
Size 5.5 kB
Tags Python 3
SHA-256 checksum
How to use checksums
52c2774a739399bbf012879fb0ba620d467bdd58e05e8442e8d7a7a94cb03762
BLAKE2b-256 checksum
How to use checksums
cefdc45c6039aa9a38c8f22a94c2a6cf350caeafc7d6404b740826f2211ea29e
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/3.1.1 pkginfo/1.5.0.1 requests/2.23.0 setuptools/41.2.0 requests-toolbelt/0.9.1 tqdm/4.46.0 CPython/3.8.2

Security for dijkstra 0.2.1

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page