# Dijkstra's implementation in rust

I would like to get any feedback about my implementation of Dijkstra algorithm in Rust following this youtube video.

Please be aware that this my first code in Rust as well as my first Dijkstra implementation in any language.

type Vertex = char;

#[derive(Debug)]
struct Connection {
peers   : (Vertex, Vertex),
weight  : u32,
}

#[derive(Debug)]
struct Graph {
connections : Vec<Connection>,
vertices    : Vec<Vertex>,
}

#[derive(Debug)]
#[derive(Clone)]
vertex     : Vertex,
distance   : u32,
via_vertex : Vertex,
}

#[derive(Debug)]
#[derive(Clone)]
struct DijkstraTable {
start_vertex : Vertex,
unvisited    : Vec<Vertex>,
}

impl DijkstraTable {
fn get_distance(&self, vertex: Vertex) -> u32 {
let mut ret = 0;

if r.vertex == vertex {
ret = r.distance;
}
}

ret
}

for r in &mut self.roads {
if r.vertex == *vertex {
return Some(r);
}
}

None
}

if r.vertex == *vertex {
return Some(r);
}
}

None
}

fn get_next_unvisited(&self) -> Option<&Vertex> {
let mut min = u32::MAX;
let mut next = None;

for v in &self.unvisited {
None => break,
Some(r) => {
if r.distance < min {
min = r.distance;
next = Some(v);
}
}
}
}
next
}

fn remove(&mut self, v : &Vertex) {
let mut index = 0;
while index < self.unvisited.len() {
let toremove = &self.unvisited[index];
if v == toremove {
self.unvisited.remove(index);
break
}
index += 1;
}
}
}

fn new(from: Vertex) -> Road {
vertex      : from,
distance    : u32::MAX,
via_vertex  : '-',
}
}
}

impl Graph {
fn get_weight(&self, peers: (Vertex, Vertex)) -> u32 {
let mut ret : u32 = 0;

for c in &self.connections {
let (a, b) = peers;

if c.peers == peers || c.peers == (b, a) {
ret = c.weight;
break;
}
}
ret
}

fn get_neighbours(&self, vertex: &Vertex) -> Vec<&Vertex> {
let mut neighbours : Vec<&Vertex> = Vec::new();

for c in &self.connections {
if c.peers.0 == *vertex {
neighbours.push(&c.peers.1);
} else if c.peers.1 == *vertex {
neighbours.push(&c.peers.0);
}
}

neighbours
}

fn vertices_from_connections(conns : &Vec<Connection>) -> Vec<Vertex> {
let mut verts : Vec<Vertex> = Vec::new();

for c in conns.iter() {
if ! verts.contains(&c.peers.0) {
verts.push(c.peers.0);
}
if ! verts.contains(&c.peers.1) {
verts.push(c.peers.1);
}
}
verts
}

fn new(conns: Vec<Connection>) -> Graph {
Graph {
vertices    : Graph::vertices_from_connections(&conns),
connections : conns,
}
}

fn dijkstra(&self, start: Vertex) -> DijkstraTable {
let mut table = DijkstraTable {
start_vertex : start,
unvisited    : self.vertices.clone(),
};

for v in &self.vertices {

if v == &start {
}

}

loop {
let xx = table.clone();
match xx.get_next_unvisited() {
None => break,
Some(v) => {
//println!("{}##################",v);
for n in self.get_neighbours(v) {
None => println!("Error"),
Some(rn) => {
let d = self.get_weight((*v, *n));
let k = d + xx.get_distance(*v);
if k < rn.distance {
rn.via_vertex = *v;
rn.distance = k;
}
}
}
}
table.remove(v);
//println!(" {:#?} ", table);
}
}
}

table
}
}

fn main() {
let graph = Graph::new(
vec![
Connection {
peers: ('A', 'B'),
weight: 6,
},
Connection {
peers: ('A', 'D'),
weight: 1,
},
Connection {
peers: ('D', 'E'),
weight: 1,
},
Connection {
peers: ('D', 'B'),
weight: 2,
},
Connection {
peers: ('E', 'B'),
weight: 2,
},
Connection {
peers: ('E', 'C'),
weight: 5,
},
Connection {
peers: ('B', 'C'),
weight: 5,
},
]
);

println!(" Dijkstra of 'A': {:#?}", graph.dijkstra('A'));

}


Edit:

The code and feedbacks are pushed to this github repo.

Many of your methods can be simplified (?) with iterators. Here's a few examples:

fn get_distance(&self, vertex: Vertex) -> u32 {
let mut ret = 0;

if r.vertex == vertex {
ret = r.distance;
}
}

ret
}


becomes

fn get_distance(&self, vertex: Vertex) -> u32 {
.iter()
.rev()
.unwrap_or(0)
}


fn get_road_mut(&mut self, vertex: &Vertex) -> Option<&mut Road> {
for r in &mut self.roads {
if r.vertex == *vertex {
return Some(r);
}
}

None
}


becomes

fn get_road_mut(&mut self, vertex: &Vertex) -> Option<&mut Road> {
.iter_mut()
}


fn remove(&mut self, v : &Vertex) {
let mut index = 0;
while index < self.unvisited.len() {
let toremove = &self.unvisited[index];
if v == toremove {
self.unvisited.remove(index);
break
}
index += 1;
}
}


becomes

fn remove(&mut self, v: &Vertex) {
let index = self.unvisited.iter().position(|vertex| vertex == v);
if let Some(index) = index {
self.unvisited.remove(index);
}
}

• Thanks @L.F. now the code looks more rust idiomatic. Aug 13, 2020 at 10:03
• The new remove() code trig a compilation issue since iterator::position return an Option. So I had to adapt it to: match self.unvisited.iter().position(|vertex| vertex==v) { None => (), Some(index) => { self.unvisited.remove(index); } } Aug 13, 2020 at 11:38
• @Zskdan That's right. I've modified the code. Aug 13, 2020 at 11:53
• I'm not sure of understanding the syntax of the new code: Does let Some(index) = index is handled as condition which return False in case of index == None and True otherwise? Aug 13, 2020 at 11:58
• Yes. if let is a control flow that works the way you described - enter the block if the let binding matches. Aug 13, 2020 at 12:54

The call to clone() in Graph::dijkstra feels wrong. Without actually re-factoring the code, I am not sure of the solution, I can see you have some problems with borrowing / mut.

My intuition is that you need to make the method that constructs DijkstraTable a method of DijkstraTable rather than Graph. It would take a (non-mutable) reference to the Graph.

Edit:

After taking a much closer look, I made some changes to eliminate the cloning ( the #derive(Clone)s are no longer needed ), and other changes:

type Vertex = char;

#[derive(Debug)]
struct Connection {
peers   : (Vertex, Vertex),
weight  : u32,
}

#[derive(Debug)]
struct Graph {
connections : Vec<Connection>,
vertices    : Vec<Vertex>,
}

#[derive(Debug)]
vertex     : Vertex,
distance   : u32,
via_vertex : Vertex,
}

#[derive(Debug)]
struct DijkstraTable {
start_vertex : Vertex,
unvisited    : Vec<Vertex>,
}

impl DijkstraTable {
fn get_distance(&self, vertex: Vertex) -> u32 {
let mut ret = 0;

if r.vertex == vertex {
ret = r.distance;
}
}

ret
}

fn get_next_unvisited(&self) -> Option<Vertex> {
let mut min = u32::MAX;
let mut next = None;

for vertex in &self.unvisited {
{
if r.vertex == *vertex
{
if r.distance < min {
min = r.distance;
next = Some(*vertex);
}
}
}
}
next
}

fn remove(&mut self, v : Vertex) {
let mut index = 0;
while index < self.unvisited.len() {
let toremove = self.unvisited[index];
if v == toremove {
self.unvisited.remove(index);
break
}
index += 1;
}
}

fn new( graph: &Graph, start: Vertex ) -> DijkstraTable {
let mut table = DijkstraTable {
start_vertex : start,
unvisited    : graph.vertices.clone(),
};

for v in &graph.vertices {

if *v == start {
}

}

loop {
match table.get_next_unvisited() {
None => break,
Some(v) => {
//println!("{}##################",v);

for n in graph.get_neighbours(v) {
let d = graph.get_weight((v, n));
let k = d + table.get_distance(v);
{
{
}
break;
}
}
}
table.remove(v);
// println!(" {:#?} ", table);
}
}
}
table
}
}

fn new(from: Vertex) -> Road {
vertex      : from,
distance    : u32::MAX,
via_vertex  : '-',
}
}
}

impl Graph {
fn get_weight(&self, peers: (Vertex, Vertex)) -> u32 {
let mut ret : u32 = 0;

for c in &self.connections {
let (a, b) = peers;

if c.peers == peers || c.peers == (b, a) {
ret = c.weight;
break;
}
}
ret
}

fn get_neighbours(&self, vertex: Vertex) -> Vec<Vertex> {
let mut neighbours : Vec<Vertex> = Vec::new();

for c in &self.connections {
if c.peers.0 == vertex {
neighbours.push(c.peers.1);
} else if c.peers.1 == vertex {
neighbours.push(c.peers.0);
}
}

neighbours
}

fn vertices_from_connections(conns : &Vec<Connection>) -> Vec<Vertex> {
let mut verts : Vec<Vertex> = Vec::new();

for c in conns.iter() {
if ! verts.contains(&c.peers.0) {
verts.push(c.peers.0);
}
if ! verts.contains(&c.peers.1) {
verts.push(c.peers.1);
}
}
verts
}

fn new(conns: Vec<Connection>) -> Graph {
Graph {
vertices    : Graph::vertices_from_connections(&conns),
connections : conns,
}
}
}

fn main() {
let graph = Graph::new(
vec![
Connection {
peers: ('A', 'B'),
weight: 6,
},
Connection {
peers: ('A', 'D'),
weight: 1,
},
Connection {
peers: ('D', 'E'),
weight: 1,
},
Connection {
peers: ('D', 'B'),
weight: 2,
},
Connection {
peers: ('E', 'B'),
weight: 2,
},
Connection {
peers: ('E', 'C'),
weight: 5,
},
Connection {
peers: ('B', 'C'),
weight: 5,
},
]
);
let dt = DijkstraTable::new( &graph, 'A' );
println!(" Dijkstra of 'A': {:#?}", dt );
}


I ought ideally to explain the changes in more detail, but I hope the above helps. In particular you had functions returning &Vertex rather than simply Vertex, which I think caused problems. Also, I have eliminated the functions get_road_mut and get_road. I'm not sure if this was strictly necessary or not, but having functions that return references is I think generally problematic.

Edit 2:

It is possible to have a function get_road that returns a mutable reference:

fn get_road(&mut self,  n: Vertex) -> &mut Road
{
{
}
}


Which is used like this:

                  let road = table.get_road( n );

• Indeed I was forced to do the clone() to handle ownership issues (Cannot borrow as immutable because it is also borrowed as mutable). I think you're right, It seems now (After reading your comment) obvious that I should move dijkstra() method to DijkstraTable. I'll try that. Thanks @George for your feedback. Aug 12, 2020 at 12:19
• Your changes makes the code more clear and clean. In fact I still don't feel comfortable with references. And when should I return references. With get_road_mut and get_road I was hoping to factorize them in a single call. But this seems not possible since they are returning different object type. Can you please elaborate on why having functions that return references is problematic ? Aug 12, 2020 at 12:49