Module shortest_path

Shortest path algorithms

This module provides various shortest path algorithms including:

• Dijkstra’s algorithm
• A* search
• Floyd-Warshall all-pairs shortest paths
• K-shortest paths (Yen’s algorithm)

Structs

AStarResult

Result of A* search algorithm

Path

Path between two nodes in a graph

Functions

astar_search

A* search algorithm for finding the shortest path with a heuristic

astar_search_digraph

A* search for directed graphs

floyd_warshall

Computes all-pairs shortest paths using the Floyd-Warshall algorithm

floyd_warshall_digraph

Computes all-pairs shortest paths for a directed graph using Floyd-Warshall

k_shortest_paths

Finds K shortest paths between two nodes using Yen’s algorithm

shortest_path

Finds the shortest path between source and target nodes using Dijkstra’s algorithm

shortest_path_digraph

Finds the shortest path in a directed graph