<Назад

Взвешенные графы

В прошлой публикации мы познакомились с общим определением графа, его реализацией в виде матрицы смежности и алгоритмом поиска в ширину. Этот алгоритм хороший, но он не будет работать для взвешенных графов.

Важно: В этой статье я буду расширять функционал матрицы смежности из прошлой статьи. Если вы еще не знакомы с кодом, то можно это сделать здесь.

В этой статье мы познакомимся со взвешенными графами, алгоритмом Дейкстры и его реализацией на языке программирования Rust.

Что такое взвешенный граф?

Взвешенный граф - это такой граф, у которого с каждым ребром связывается число, называемое весом.

Вот как он выглядит:

Для поиска оптимального пути в таких графах используется алгоритм Дейкстры.

Алгоритм Дейкстры

Марк проспал, и он опаздывает на работу. Ему нужна помощь в выборе быстрого маршрута до работы. Вот так выглядит граф этой задачи:

Самый оптимальный маршрут выглядит так:

Основное назначение алгоритма Дейкстры - поиск пути с наименьшей стоимостью.

Алгоритм состоит из нескольких шагов:

1. Найти узел с наименьшей стоимость.
2. Обновить стоимость соседей этого узла.
3. Повторять, пока не будут пройдены все узлы.
4. Вычислить итоговый путь.

Применим алгоритм к нашей задаче.

Шаг 1:

1. Первый наименьший сосед B = 1 мин;
2. Стоимость прохождения пути Дом -> B -> С = 3 мин, а Дом -> B -> D = 8 мин.

Шаг 2:

1. Следующий узел - A = 2 мин;
2. Стоимость прохождения пути Дом -> A -> D = 4 мин, а Дом -> А -> C = 8 мин.

После этих шагов мы получаем следующие данные:

Дом -> B -> C = 3 мин - наиболее оптимальный путь до точки C, запоминаем

Дом -> B -> D = 8 мин

Дом -> A -> D = 4 мин - наиболее оптимальный путь до точки D, запоминаем

Дом -> A -> C = 7 мин

После этих шагов осталось два узла C и D.

Шаг 4:

1. Узел с наименьшей стоимостью C = 3 мин;
2. Стоимость прохождения пути Дом -> B -> C -> Работа = 13 мин.

Шаг 5:

1. Следующий узел - D = 4 мин;
2. Стоимость прохождения пути Дом -> A -> D -> Работа = 6 мин.

Получает, что самый быстрый путь до работы - Дом -> A -> D.

ВАЖНО: Ребра взвешенного графа могут быть с отрицательными весами. Для таких графов алгоритм Дейкстры не работает, но существует алгоритм Беллмана-Форда, который поможет решить задачу.

А теперь перейдем к реализации нашего алгоритма.

Реализация

Добавим для структуры Matrix добавим функцию, которая будет вычислять индекс узла с минимальным весом.

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;
    }
}

Теперь опишем базовую версию алгоритма, которая вычисляет оптимальная стоимость для каждого узла графа. В dist будем хранить оптимальные стоимость, где индекс - это номер узла. В векторе done храним информацию о пройденных узлах.

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);
    }
}

Хочется, чтобы алгоритм выводил оптимальный путь и стоимость для конкретного узла. Давайте модернизируем алгоритм. Создадим вектор path, индекс которого соответствует узлу, а значение по индексу предшествующему оптимальному узлу. Еще на входе алгоритма будем принимать индекс интересующего нас узла.

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));
  }
}

Теперь самое время протестировать алгоритм на нашей задаче.

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);
    }
}

На выходе:
Weights sum: 6
Path: [0, 1, 4, 5]