Single Source Shortest Path (DAG)

Finds the single source shortest path of a Directed Acyclic Graph (DAG).

Usage

sssp_dag(graph: Graph, source: int)

Parameters:
      graph : Graph
            Graph Object
      source : int
            Source Vertex

Returns:
      dict
            A dictionary of vertex -> cost

Example

from jellybeans.algos import sssp_dagfrom jellybeans.structures import Graphg = Graph()g.add_vertex(0)g.add_vertex(1)g.add_vertex(2)g.add_vertex(3)g.add_vertex(4)g.add_edge(0, 2, 6)g.add_edge(0, 1, 2)g.add_edge(0, 3, 7)g.add_edge(1, 3, 3)g.add_edge(1, 4, 6)g.add_edge(2, 4, 1)g.add_edge(3, 4, 5)res = sssp_dag(g, 0)print(res) # {0: 0, 1: 2, 2: 6, 3: 5, 4: 7}