Shortest Path Algorithms

Dijkstra's Algorithm

Category: Shortest Path Time: O((V + E) log V) with a binary heap Constraint: Non-negative edge weights only

Dijkstra's algorithm finds the shortest path from a source node to all reachable nodes.

Implementation

Uses Rust's BinaryHeap as a max-heap with negated distances (Rust's BinaryHeap is a max-heap, so distances are stored as negative values for min-heap behavior):

fn dijkstra(&self, start: usize) -> (Vec<usize>, Vec<f64>) {
    let n = self.compact_to_id.len();
    let start_compact = self.id_to_compact[&start];

    let mut dist = vec![f64::INFINITY; n];
    let mut prev = vec![usize::MAX; n];
    let mut heap = BinaryHeap::new();

    dist[start_compact] = 0.0;
    heap.push(OrderedFloat(-0.0), start_compact);

    while let Some((neg_d, u)) = heap.pop() {
        let d = -neg_d;
        if d > dist[u] { continue; }

        for &(v_id, w) in &self.adjacency[&self.compact_to_id[u]] {
            let v = self.id_to_compact[&v_id];
            let nd = d + w;
            if nd < dist[v] {
                dist[v] = nd;
                prev[v] = u;
                heap.push(OrderedFloat(-nd), v);
            }
        }
    }
    // Reconstruct path from prev array...
    (path, dist)
}

Output

• path — shortest path to the furthest reachable node (or to end_node if specified)
• distances — map of all reachable node IDs to their shortest distance from source

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"dijkstra","file_format":"edge_list","start_node":0}'

---

A* Search

Category: Shortest Path Time: O(E log V) in practice (depends on heuristic quality) Constraint: Non-negative edge weights

A* improves on Dijkstra for single-target shortest paths by using a heuristic function to guide the search toward the goal.

Heuristic

This implementation uses a uniform heuristic h=1 — appropriate when node positions are not known (no spatial coordinates). This makes A* equivalent to a slightly modified Dijkstra in practice, but the implementation correctly supports a real heuristic when coordinates are available.

Implementation

Open set implemented as a BinaryHeap with f = g + h priority:

fn astar(&self, start: usize, end: usize) -> Vec<usize> {
    let mut open_set = BinaryHeap::new();
    let mut g_score = HashMap::new();

    g_score.insert(start, 0.0f64);
    open_set.push(AStarNode { f: 0.0, id: start });

    while let Some(AStarNode { id: current, .. }) = open_set.pop() {
        if current == end { return reconstruct_path(&came_from, end); }

        for &(neighbor, weight) in &self.adjacency[&current] {
            let tentative_g = g_score[&current] + weight;
            if tentative_g < *g_score.get(&neighbor).unwrap_or(&f64::INFINITY) {
                came_from.insert(neighbor, current);
                g_score.insert(neighbor, tentative_g);
                let f = tentative_g + 1.0; // h = 1
                open_set.push(AStarNode { f: -f, id: neighbor });
            }
        }
    }
    vec![] // no path found
}

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"astar","file_format":"edge_list","start_node":0,"end_node":4}'

Visualization

A* animates the path from start (green) to end (red). Intermediate path nodes are highlighted in cyan.

---

Bellman-Ford

Category: Shortest Path Time: O(V × E) Advantage over Dijkstra: Handles negative edge weights; detects negative cycles

Implementation

V−1 relaxation passes followed by a V-th detection pass:

fn bellman_ford(&self, start: usize) -> (Vec<usize>, Vec<f64>, bool) {
    let n = self.compact_to_id.len();
    let mut dist = vec![f64::INFINITY; n];
    dist[start_compact] = 0.0;

    // V-1 relaxation passes
    for _ in 0..n - 1 {
        for (&u_id, neighbors) in &self.adjacency {
            let u = self.id_to_compact[&u_id];
            if dist[u] == f64::INFINITY { continue; }
            for &(v_id, w) in neighbors {
                let v = self.id_to_compact[&v_id];
                if dist[u] + w < dist[v] {
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                }
            }
        }
    }

    // V-th pass: detect negative cycles
    let mut has_negative_cycle = false;
    for (&u_id, neighbors) in &self.adjacency {
        let u = self.id_to_compact[&u_id];
        if dist[u] == f64::INFINITY { continue; }
        for &(v_id, w) in neighbors {
            let v = self.id_to_compact[&v_id];
            if dist[u] + w < dist[v] {
                has_negative_cycle = true;
                break;
            }
        }
    }

    (path, dist, has_negative_cycle)
}

Negative Cycle Detection

If has_negative_cycle: true is returned, the frontend displays a warning banner instead of path results — shortest paths are undefined when a reachable negative cycle exists.

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"bellman_ford","file_format":"edge_list","start_node":0}'

API Response

{
  "path": [0, 2, 3, 4],
  "distances": { "0": 0.0, "2": -1.5, "3": 0.5 },
  "has_negative_cycle": false,
  "mpi_processes": 2,
  "mpi_mode": "distributed"
}