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
//! A Dijkstra's algorithm implementation that aims to be simple to use and fast to run
//!
//! This is the central pillar of `dijkstra_suite` crate.
//! `dijkstra` module implements the algorithm logic, exposes the main function to compute
//! the shortest path and provides the interface to the core parts of implementation
//!
//! ## Versioned implementations for multi-strategy support
//!
//! Main implementation should be `v1` and that should be used for "default exports" from
//! `dijkstra` module
//!
//! Versioned submoduling allows multiple implementations to live and be maintened together
//! and easily switched
//!
//! ## Usage
//!
//! Create a `Graph`, define the start and the end node ids, then call `dijkstra_path()` function.
//! Returned result is a sequence of node ids that represents the shortest path possible
//!
//! ```rust
//! use dijkstra_suite::dijkstra::dijkstra_path;
//! use dijkstra_suite::graph::Graph;
//! use dijkstra_suite::path::Path;
//! use dijkstra_suite::node::{Node, NodeConnection};
//!
//! let mut graph: Graph<&str, f32> = Graph::default();
//! let node_a = Node {
//! id: "A",
//! weight: 0.0,
//! neighbours: vec![
//! NodeConnection {
//! from: "A",
//! to: "B",
//! weight: 7.0,
//! },
//! NodeConnection {
//! from: "A",
//! to: "E",
//! weight: 1.0,
//! },
//! ],
//! };
//!
//! let node_b = Node {
//! id: "B",
//! weight: 0.0,
//! neighbours: vec![
//! NodeConnection {
//! from: "B",
//! to: "A",
//! weight: 7.0,
//! },
//! NodeConnection {
//! from: "B",
//! to: "C",
//! weight: 3.0,
//! },
//! NodeConnection {
//! from: "B",
//! to: "E",
//! weight: 8.0,
//! },
//! ],
//! };
//!
//! let node_c = Node {
//! id: "C",
//! weight: 0.0,
//! neighbours: vec![
//! NodeConnection {
//! from: "C",
//! to: "B",
//! weight: 3.0,
//! },
//! NodeConnection {
//! from: "C",
//! to: "D",
//! weight: 6.0,
//! },
//! NodeConnection {
//! from: "C",
//! to: "E",
//! weight: 2.0,
//! },
//! ],
//! };
//!
//! let node_d = Node {
//! id: "D",
//! weight: 0.0,
//! neighbours: vec![
//! NodeConnection {
//! from: "D",
//! to: "C",
//! weight: 6.0,
//! },
//! NodeConnection {
//! from: "D",
//! to: "E",
//! weight: 7.0,
//! },
//! ],
//! };
//!
//! let node_e = Node {
//! id: "E",
//! weight: 0.0,
//! neighbours: vec![
//! NodeConnection {
//! from: "E",
//! to: "A",
//! weight: 1.0,
//! },
//! NodeConnection {
//! from: "E",
//! to: "B",
//! weight: 8.0,
//! },
//! NodeConnection {
//! from: "E",
//! to: "C",
//! weight: 2.0,
//! },
//! NodeConnection {
//! from: "E",
//! to: "D",
//! weight: 7.0,
//! },
//! ],
//! };
//!
//! graph.insert(node_a.id, node_a);
//! graph.insert(node_b.id, node_b);
//! graph.insert(node_c.id, node_c);
//! graph.insert(node_d.id, node_d);
//! graph.insert(node_e.id, node_e);
//!
//! let result = dijkstra_path(&graph, "B", "D");
//!
//! let expected_path: Path<&str, f32> = Path {
//! weight: 9.0,
//! steps: vec!["B", "C", "D"],
//! };
//!
//! assert_eq!(result.unwrap(), expected_path)
//!
//! ```