Module dijkstra 

Dijkstra’s Algorithm

Finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. One of the most famous algorithms in computer science.

Time complexity: O((V + E) log V) with binary heap

Examples

use advanced_algorithms::graph::{Graph, dijkstra};

let mut graph = Graph::new(5);
graph.add_edge(0, 1, 4.0);
graph.add_edge(0, 2, 1.0);
graph.add_edge(2, 1, 2.0);
graph.add_edge(1, 3, 1.0);
graph.add_edge(2, 3, 5.0);

let result = dijkstra::shortest_path(&graph, 0);
assert_eq!(result.distance[3], 4.0); // 0->2->1->3

Structs

ShortestPathResult

Result of Dijkstra’s algorithm

Functions

shortest_path

Computes shortest paths from source to all nodes using Dijkstra’s algorithm

shortest_path_to_target

Finds shortest path from source to a specific target node