uni_algo/algo/algorithms/
dijkstra.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Dijkstra's Shortest Path Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use std::cmp::Reverse;
9use std::collections::BinaryHeap;
10use uni_common::core::id::Vid;
11
12pub struct Dijkstra;
13
14#[derive(Debug, Clone)]
15pub struct DijkstraConfig {
16    pub source: Vid,
17    pub target: Option<Vid>,
18    pub max_distance: Option<f64>,
19}
20
21impl Default for DijkstraConfig {
22    fn default() -> Self {
23        Self {
24            source: Vid::from(0),
25            target: None,
26            max_distance: None,
27        }
28    }
29}
30
31pub struct DijkstraResult {
32    pub distances: Vec<(Vid, f64)>,
33    pub path: Option<Vec<Vid>>,
34}
35
36impl Algorithm for Dijkstra {
37    type Config = DijkstraConfig;
38    type Result = DijkstraResult;
39
40    fn name() -> &'static str {
41        "shortestPath"
42    }
43
44    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
45        let source_slot = match graph.to_slot(config.source) {
46            Some(slot) => slot,
47            None => {
48                return DijkstraResult {
49                    distances: Vec::new(),
50                    path: None,
51                };
52            }
53        };
54
55        let n = graph.vertex_count();
56        let mut dist = vec![f64::INFINITY; n];
57        let mut prev: Vec<Option<u32>> = vec![None; n];
58        let mut heap = BinaryHeap::new();
59
60        dist[source_slot as usize] = 0.0;
61        heap.push(Reverse((0.0f64.to_bits(), source_slot)));
62
63        let target_slot = config.target.and_then(|t| graph.to_slot(t));
64
65        while let Some(Reverse((d_bits, u))) = heap.pop() {
66            let d = f64::from_bits(d_bits);
67            if d > dist[u as usize] {
68                continue;
69            }
70
71            // Early exit for point-to-point
72            if target_slot == Some(u) {
73                break;
74            }
75
76            // Max distance cutoff
77            if let Some(max_d) = config.max_distance
78                && d > max_d
79            {
80                continue;
81            }
82
83            for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
84                let weight = if graph.has_weights() {
85                    graph.out_weight(u, i)
86                } else {
87                    1.0
88                };
89                let new_dist = d + weight;
90
91                if new_dist < dist[v as usize] {
92                    dist[v as usize] = new_dist;
93                    prev[v as usize] = Some(u);
94                    heap.push(Reverse((new_dist.to_bits(), v)));
95                }
96            }
97        }
98
99        // Reconstruct path if target specified
100        let mut path = None;
101        if let Some(t_slot) = target_slot
102            && dist[t_slot as usize] < f64::INFINITY
103        {
104            let mut p = Vec::new();
105            let mut curr = Some(t_slot);
106            while let Some(slot) = curr {
107                p.push(graph.to_vid(slot));
108                if slot == source_slot {
109                    break;
110                }
111                curr = prev[slot as usize];
112            }
113            p.reverse();
114            path = Some(p);
115        }
116
117        let results = dist
118            .into_iter()
119            .enumerate()
120            .filter(|(_, d)| *d < f64::INFINITY)
121            .map(|(slot, d)| (graph.to_vid(slot as u32), d))
122            .collect();
123
124        DijkstraResult {
125            distances: results,
126            path,
127        }
128    }
129}
uni_algo/algo/algorithms/dijkstra.rs

uni_algo/algo/algorithms/
dijkstra.rs
