weighted_path 0.6.0

A Rust library for finding shortest paths in weighted graphs using Dijkstra's algorithm with multiple heap implementations
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

use crate::fibonacci::FibonacciHeap;
use std::cell::RefCell;
use std::rc::Rc;

use crate::dijkstra::heap_trait::PriorityQueue;

// Implement PriorityQueue trait directly on FibonacciHeap
impl PriorityQueue for FibonacciHeap {
    type Handle = Rc<RefCell<crate::fibonacci::Node>>;

    fn insert(&mut self, key: u32, node_id: usize) -> Self::Handle {
        FibonacciHeap::insert(self, key, node_id)
    }

    fn extract_min(&mut self) -> Option<(u32, usize)> {
        FibonacciHeap::extract_min(self)
    }

    fn supports_decrease_key(&self) -> bool {
        true
    }

    fn decrease_key(&mut self, handle: &Self::Handle, new_key: u32) {
        FibonacciHeap::decrease_key(self, handle, new_key);
    }
}

/// Dijkstra implementation using the safe `Rc<RefCell>` Fibonacci heap.
///
/// Memory-safe but slower than the raw-pointer variant due to Rc/RefCell overhead.
/// This is a thin wrapper around the generic Dijkstra implementation.
pub fn dijkstra_fibonacci(
    start: usize,
    end: usize,
    graph: &[Vec<(usize, u32)>],
) -> (Vec<usize>, Option<u32>) {
    crate::dijkstra::dijkstra(start, end, graph, FibonacciHeap::new())
}