dijkstra 0.2.0

dijkstra is a native Python implementation of Dijkstra's shortest path algorithm.

Dijkstra

Package author: Jukka Aho (@ahojukka5, [e-mail])

Package implements Dijkstra's shortest path finding algorithm.

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 = 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)

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 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)