Demonstration of the Dijkstra algorithm for educational purposes
Project description
teachmedijkstra
This package contains an implementation of the Dijkstra's algorithm for finding the shortest paths in a graph and serves to educational purposes.
Its main goal is to produce a LaTeX document which contains:
- description of the performing of the Dijkstra's algorithm in a for of a table where each row corresponds to a vertex of the graph and each column corresponds to one time step of the algorithm,
- shortest path tree (or shortest path covering) which is a subgraph of the processed graph that contains those edges that belong the shortest paths.
The main motivation to write this program was to have a tool to automatically generate examen tests on Dijkstra's algorithm with randomly created graphs and with the corresponding solutions which consist of two items described in the list above.
Installation
Install the package from PyPI utilizing the pip module:
python -m pip install teachmedijkstra
Example
What follows is a simple program using the package teachmedijkstra
.
It defines an undirected weighted graph with six vertices, performs the
Dijkstra's algorithm to find the shortest paths starting from the vertex "a",
and exports the result to a LaTeX file "example.tex".
import teachmedijkstra
graph = teachmedijkstra.UndirectedGraph()
graph.addVertex("a", (0,2))
graph.addVertex("b", (1,2))
graph.addVertex("c", (2,2))
graph.addVertex("d", (0,1))
graph.addVertex("e", (1,1))
graph.addVertex("f", (2,1))
graph.addEdge("a", "b", 7)
graph.addEdge("b", "c", 8)
graph.addEdge("d", "e", 6)
graph.addEdge("e", "f", 1)
graph.addEdge("a", "d", 5)
graph.addEdge("b", "e", 2)
graph.addEdge("c", "f", 4)
graph.addEdge("a", "e", 3)
graph.addEdge("b", "f", 9)
dijkstra = teachmedijkstra.Dijkstra(graph, "a")
dijkstra.run()
dijkstra.saveToLaTeXFile("example.tex")
More Examples
For more examples see the following programs:
- example_undirected.py ... example of performing the Dijkstra's algorithm on an undirected weighted graph with 9 vertices,
- example_directed.py ... example of performing the Dijkstra's algorithm on a directed weighted graph with 9 vertices,
- example_random.py ... example of creating a number of exercises on Dijkstra's algorithm with randomly generated graphs.
Documentation
The comments in the code of the program are written with respect to produce a nicely written documentation when using pdoc3 (see also the PyPI page of pdoc3). In order to create the HTML document with the program documentation, install first pdoc3 from PyPI utilizing the pip module:
python -m pip install pdoc3
Once installed, run this command from the root directory of the project:
pdoc3 --html teachmedijkstra
A directory html/ that contains the documentation will be created.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for teachmedijkstra-0.1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 36e129d93e724cd44b1e0b67e4aae91aeef880b4c204b959cef2b74ac8f0b913 |
|
MD5 | 5ad2d22401afae551785bf25f9a2ef21 |
|
BLAKE2b-256 | 8e6d5164e74fe69afa2cc9dd2bd0d5a3f367908c5cf173f0910a24232109fcff |