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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
// SPDX-License-Identifier: Apache-2.0
// Copyright 2024-2026 Dragonscale Team
//! Dijkstra's Shortest Path Algorithm.
use crate::algo::GraphProjection;
use crate::algo::algorithms::Algorithm;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use uni_common::core::id::Vid;
pub struct Dijkstra;
#[derive(Debug, Clone)]
pub struct DijkstraConfig {
pub source: Vid,
pub target: Option<Vid>,
pub max_distance: Option<f64>,
}
impl Default for DijkstraConfig {
fn default() -> Self {
Self {
source: Vid::from(0),
target: None,
max_distance: None,
}
}
}
pub struct DijkstraResult {
pub distances: Vec<(Vid, f64)>,
pub path: Option<Vec<Vid>>,
}
/// Error returned when Dijkstra cannot produce a correct result.
///
/// Dijkstra's settled-on-first-pop invariant only holds for non-negative
/// edge weights, so a negative weight is rejected rather than silently
/// yielding a wrong shortest distance.
#[derive(Debug, Clone)]
pub enum DijkstraError {
/// An edge from `source` to `target` carries a negative `weight`.
NegativeEdge {
source: Vid,
target: Vid,
weight: f64,
},
}
impl std::fmt::Display for DijkstraError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
DijkstraError::NegativeEdge {
source,
target,
weight,
} => write!(
f,
"Dijkstra rejects negative edge {source:?} -> {target:?} (weight {weight})"
),
}
}
}
impl std::error::Error for DijkstraError {}
impl Algorithm for Dijkstra {
type Config = DijkstraConfig;
type Result = Result<DijkstraResult, DijkstraError>;
fn name() -> &'static str {
"shortestPath"
}
fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
// Reject negative weights up front: Dijkstra's correctness relies on
// non-negative edges, so any negative weight is a hard error rather
// than a silently wrong answer.
if graph.has_weights() {
let n = graph.vertex_count();
for u in 0..n as u32 {
for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
let weight = graph.out_weight(u, i);
if weight < 0.0 {
return Err(DijkstraError::NegativeEdge {
source: graph.to_vid(u),
target: graph.to_vid(v),
weight,
});
}
}
}
}
let source_slot = match graph.to_slot(config.source) {
Some(slot) => slot,
None => {
return Ok(DijkstraResult {
distances: Vec::new(),
path: None,
});
}
};
let n = graph.vertex_count();
let mut dist = vec![f64::INFINITY; n];
let mut prev: Vec<Option<u32>> = vec![None; n];
let mut heap = BinaryHeap::new();
dist[source_slot as usize] = 0.0;
heap.push(Reverse((0.0f64.to_bits(), source_slot)));
let target_slot = config.target.and_then(|t| graph.to_slot(t));
while let Some(Reverse((d_bits, u))) = heap.pop() {
let d = f64::from_bits(d_bits);
if d > dist[u as usize] {
continue;
}
// Early exit for point-to-point
if target_slot == Some(u) {
break;
}
// Max distance cutoff
if let Some(max_d) = config.max_distance
&& d > max_d
{
continue;
}
for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
let weight = if graph.has_weights() {
graph.out_weight(u, i)
} else {
1.0
};
let new_dist = d + weight;
if new_dist < dist[v as usize] {
dist[v as usize] = new_dist;
prev[v as usize] = Some(u);
heap.push(Reverse((new_dist.to_bits(), v)));
}
}
}
// Reconstruct path if target specified
let mut path = None;
if let Some(t_slot) = target_slot
&& dist[t_slot as usize] < f64::INFINITY
{
let mut p = Vec::new();
let mut curr = Some(t_slot);
while let Some(slot) = curr {
p.push(graph.to_vid(slot));
if slot == source_slot {
break;
}
curr = prev[slot as usize];
}
p.reverse();
path = Some(p);
}
let results = dist
.into_iter()
.enumerate()
.filter(|(_, d)| *d < f64::INFINITY)
.map(|(slot, d)| (graph.to_vid(slot as u32), d))
.collect();
Ok(DijkstraResult {
distances: results,
path,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algo::test_utils::build_test_graph;
/// Regression: Dijkstra must reject negative edge weights with an error.
///
/// Dijkstra's settled-on-first-pop guard (`if d > dist[u] { continue }`)
/// and `to_bits()` heap key are only valid for non-negative weights, so a
/// negative weight would silently yield a wrong shortest distance instead
/// of the true minimum. The chosen contract is to reject such input with a
/// clean [`DijkstraError::NegativeEdge`].
// Rust guideline compliant
#[test]
fn test_dijkstra_rejects_or_handles_negative_weight() {
// Edges: 0->1 = 2, 0->2 = 5, 2->1 = -4.
// True shortest 0 -> 2 -> 1 = 5 + (-4) = 1, beating the direct 0 -> 1 = 2.
let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
let edges = vec![
(Vid::from(0), Vid::from(1)),
(Vid::from(0), Vid::from(2)),
(Vid::from(2), Vid::from(1)),
];
let mut graph = build_test_graph(vids, edges);
// Flattened CSR weights, matching out-adjacency layout:
// Node 0: [0->1 = 2.0, 0->2 = 5.0]
// Node 1: []
// Node 2: [2->1 = -4.0]
graph.out_weights = Some(vec![2.0, 5.0, -4.0]);
let config = DijkstraConfig {
source: Vid::from(0),
target: Some(Vid::from(1)),
max_distance: None,
};
// The negative edge 2 -> 1 must be rejected, not silently mis-routed.
assert!(matches!(
Dijkstra::run(&graph, config),
Err(DijkstraError::NegativeEdge { .. })
));
}
}