Dijkstra
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)
| 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)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| 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.