<Назад
Взвешенные графы

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


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


В этой статье мы познакомимся со взвешенными графами, алгоритмом Дейкстры и его реализацией на языке программирования 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]
Хэштеги:
#алгоритмы
#графы
Поделиться:

Самое свежее

Простыми словами о графах

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

#графы
#rust
#алгоритмы

В чем отличие аутсорсинга разработки от аутстаффинга ИТ-сотрудника для разработки?

В этой статье разберемся, что такое аутсорс- и аутстафф-разработка.

#процессразработки

Знакомьтесь, Пентест

Начинаем рассматривать один из основных методов оценки безопасности компьютерных систем и сетей на предмет потенциальных уязвимостей - тестирование на проникновение

#пентест

Сокращаем срок реализации MVP

Разберемся со сроками реализации MVP.

#процессразработки

Тестирование концепции MVP

Разбираемся с тем, как не потратить бюджеты на разработку MVP впустую

#процессразработки

Неверная оценка стоимости услуг ИТ подрядчика

Сегодня мы поговорим о неверной оценке стоимости разработки ИТ решений. Эта боль - одна из основных для предприятий и стартапов, включая самих ИТ подрядчиков.

#консалтинг

Введение в паттерны проектирования в разработке программного обеспечения

В этой статье мы начнем погружаться в мир оптимизации архитектуры приложений с помощью шаблонов проектирования

#шаблоныпроектирования

Уровни модели OSI

В этой статье мы более подробно рассмотрим каждый из уровней модели OSI

#сети
#osi

Документирование кода в языке программирования Rust

В этой статье рассмотрим то, как происходит документирование в Rust и рассмотрим очень полезную возможность - написание тестов через документирование.

#rust

Знакомство с моделью OSI

В этой статье начинаем рассматривать фундаментальную модель сетевого взаимодействия - OSI

#сети

CSS анимация пульсации

Простой пример того, как реализовать анимацию пульсации, используя HTML и CSS

#css

От концепции к MVP

В этой статье вы узнаете, на примере, о том, как перейти от концепции к MVP без лишних усложнений в функционале продукта

#процессразработки

Введение в написание технического задания

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

#процессразработки

Введение в разработку

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

#процессразработки

От идеи к концепции

В этой публикации мы поговорим о том, чем идея отличается от концепции. Сделаем это на примере конкретной цели

#процессразработки

Зачем VPN бизнесу?

В этой статье мы рассмотрим то, как можно обезопасить доступ к облачным ресурсам предприятия с помощью VPN

#сети
#впн