An Implementation of a solution to the Single-source shortest path problem which leverages the Topological order of the underlying graph (in Python).

``````import math

from typing import List, Mapping, TypeVar, Generic
from dataclasses import dataclass, field
from itertools import count

T = TypeVar('T')
NodeId = int
EdgeWeight = int
Edges = Mapping[NodeId, Mapping[NodeId, EdgeWeight]]
Previouses = Mapping[NodeId, NodeId]
Distances = Mapping[NodeId, EdgeWeight]

@dataclass
class Node(Generic[T]):
value: T
id: NodeId = field(defualt_factory=count().__next__)

def single_source_shortest_path(target_id: NodeId, topological_ordering: List[NodeId], edges: Edges) -> Tuple[Previouses, Distances]:
"""Find the shortest paths from TARGET_ID to all vertices in EDGES which are connected to TARGET_ID.

Return a tuple of:
- previouses: Mapping from Node.id to the previous Node.id in the shortest path
- distances: Mapping from Node.id to the distance from TARGET_ID to that Node"""

distances = {}
previouses = {}

for node_id in edges:
distances[node_id] = math.inf
previouses[node_id] = None

distances[target_id] = 0

def visit(node_id: NodeId) -> None:
for neighbor_id, edge_weight in [(neighbor_id, edges[node_id][neighbor_id]) for neighbor_id in edges[node_id]]:
if distances[neighbor_id] > distances[node_id] + edge_weight:
distances[neighbor_id] = distances[node_id] + edge_weight
previouses[neighbor_id] = node_id

visit(target_id)
for node_id in [id for id in topological_ordering if id != target_id]:
visit(node_id)

return distances, previouses
``````