<Back

Weighted graphs

In a previous article, we got acquainted with the general definition of a graph, its implementation in the form of an adjacency matrix, and the basic algorithm for breadth-first search. This algorithm is good, but it won't work for a weighted graph.

Important: In this article I will expand the functionality of the adjacency matrix from the last article. If you are not familiar with the code yet, you can do it here or read the previous article.

We will get acquainted with weighted graphs, Dijkstra's algorithm, and its implementation in the Rust programming language.

What is a weighted graph?

A weighted graph is a graph that has a number associated with each edge, called a weight.

Here's what it looks like:

Dijkstra's algorithm is used to find the optimal path in such graphs.

Dijkstra's algorithm

Mark overslept, and he's late for work. He needs help choosing a quick path to work. This is what the graph of this problem looks like:

The most optimal path looks like this:

The main purpose of Dijkstra's algorithm is to find the path with the lowest cost.

The algorithm consists of several steps:

1. Find the node with the lowest cost.
2. Update the cost of the neighbors of this node.
3. Repeat until all nodes are passed.
4. Calculate the final path.

Let's apply the algorithm to our problem.

Step 1:

   The first smallest neighbor B = 1 min;

   The cost of passing the path Home -> B -> C = 3 min, and Home -> B -> D = 8 min.

Step 2:

   The next node is A = 2 min;

   The cost of passing the path Home -> A -> D = 4 min, and Home -> A -> C = 8 min.

After these steps we get the following data:

Home -> B -> C = 3 min - the most optimal way to point C, let's remember it

Home -> B -> D = 8 min

Home -> A -> D = 4 min - the most optimal way to point D, let's remember it

House -> A -> C = 7 min

After these steps, there are two nodes C and D.

Step 4:

   The node with the lowest cost C = 3 min;

   The cost of passing the way Home -> B -> C -> Work = 13 min.

Step 5:

   The next node is D = 4 min;

   The cost of passing the way Home -> A -> D -> Work = 6 min.

Gets that the fastest way to work is Home -> A -> D.

IMPORTANT: The edges of a weighted graph can be with negative weights. Dijkstra's algorithm does not work for such graphs, but there is a Bellman-Ford algorithm that will help solve the problem.

And now let's move on to the implementation of our algorithm.

Implementation

Let's add a function for the Matrix structure that will calculate the index of the node with the minimum weight.

use std::i32::MAX;

impl Matrix {
    pub fn min_distance(&self, dists: &mut Vec<i32>, done: &mut Vec<bool>) -> usize {
        let mut min = MAX;
        let mut min_node = 0;
        for v in 0..self.n {
            if !done[v] && dists[v] <= min {
                min = dists[v];
                min_node = v;
            }
        }
        return min_node;
    }
}

Now we describe a basic version of the algorithm that calculates the optimal cost for each node of the graph. In dist we will store the optimal cost, where the index is the node number. In the done vector, we store information about passed nodes.

impl Matrix {
    pub fn dijsktra(&self, start_node: usize) {
        let mut dists: Vec<i32> = vec![MAX; self.n];
        let mut done: Vec<bool> = vec![false; self.n];
        dists[start_node] = 0;
        for _ in 0..(self.n - 1) {
            let min_node = self.min_distance(&mut dists, &mut done);
            done[min_node] = true;
            for adj_node in 0..self.n {
                let not_zero = self[min_node][adj_node] != 0;
                let new_dist = dists[min_node] + self[min_node][adj_node];
                if !done[adj_node]
                    && not_zero
                    && dists[min_node] != MAX
                    && new_dist < dists[adj_node]
                {
                    path[adj_node] = min_node;
                    dists[adj_node] = new_dist;
                }
            }
        }
        println!("Distances: {:?}", dists);
    }
}

I want the algorithm to output the optimal path and cost for a particular node. Let's upgrade the algorithm. Let's create a path vector, the index of which corresponds to the node, and the index value preceding the optimal node. Even at the input of the algorithm, we will take the index of the node we are interested in.

pub fn dijsktra(&self, start_node: usize, target_node: usize) -> Option<(i32, Vec<usize>)> {
      let mut dists: Vec<i32> = vec![MAX; self.n];
      let mut done: Vec<bool> = vec![false; self.n];
      dists[start_node] = 0;
      let mut path: Vec<usize> = vec![0; self.n];
      for _ in 0..(self.n - 1) {
          let min_node = self.min_distance(&mut dists, &mut done);
          done[min_node] = true;
          for adj_node in 0..self.n {
              let not_zero = self[min_node][adj_node] != 0;
              let new_dist = dists[min_node] + self[min_node][adj_node];
              if !done[adj_node]
                  && not_zero
                  && dists[min_node] != MAX
                  && new_dist < dists[adj_node]
              {
                  path[adj_node] = min_node;
                  dists[adj_node] = new_dist;
              }
          }
      }
      if dists[target_node] == MAX {
          return None;
      }
      let mut target_path = path[target_node];
      let mut final_path = vec![target_node];
      while !final_path.contains(&0) {
          final_path.push(target_path);
          target_path = path[target_path];
      }
      final_path.reverse();
      return Some((dists[target_node], final_path));
  }
}

Now is the time to test the algorithm on our graph.

fn main() {
    
    // Node 0 - Home

    // Node 1 - A

    // Node 2 - B

    // Node 3 - C

    // Node 4 - D

    // Node 5 - Work

    let mut graph: Matrix = Matrix::new(6, 0);
    graph.add_w_directed_edge(0, 1, 2);
    graph.add_w_directed_edge(0, 2, 1);
    graph.add_w_directed_edge(1, 3, 6);
    graph.add_w_directed_edge(1, 4, 2);
    graph.add_w_directed_edge(2, 3, 2);
    graph.add_w_directed_edge(2, 4, 7);
    graph.add_w_directed_edge(3, 5, 10);
    graph.add_w_directed_edge(4, 5, 2);
    let res = graph.dijsktra(0, 5);
    if res.is_some() {
        let res = res.unwrap();
        println!("Weights sum: {:?}", res.0);
        println!("Path: {:?}", res.1);
    }
}

Output: 
Weights sum: 6
Path: [0, 1, 4, 5]