Алгоритм Дейкстры на языке C

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

Алгоритм Дейкстры — один из основных алгоритмов для нахождения кратчайшего пути во взвешенном графе с неотрицательными весами ребер. Данный алгоритм был предложен нидерландским ученым Эдсгером Дейкстрой в 1956 году. Алгоритм Дейкстры является эффективным и широко применяемым в компьютерных науках.

Идея алгоритма Дейкстры

Идея алгоритма Дейкстры заключается в том, что на каждой итерации происходит поиск вершины с наименьшей оценкой (расстоянием) от начальной вершины до текущей вершины. Затем оценка для всех соседей этой текущей вершины пересчитывается и обновляется, если новая оценка меньше имеющейся. Этот процесс повторяется до тех пор, пока все вершины не будут просмотрены.

Процесс работы алгоритма Дейкстры

1. Инициализация. Устанавливаем начальную вершину, к которой ищем кратчайший путь. Для этой вершины устанавливаем оценку равной 0, а для всех остальных вершин устанавливаем оценку равной бесконечности.
2. Выбор текущей вершины. Из необозреваемых вершин выбираем ту, у которой имеется наименьшая оценка, и называем ее текущей вершиной.
3. Обновление оценок. Для каждой соседней вершины текущей вершины пересчитываем оценку, если новая оценка меньше имеющейся.
4. Отметка текущей вершины как посещенной. После пересчета оценок для всех соседей текущей вершины, ее можно отметить как посещенную, чтобы исключить ее из дальнейшего рассмотрения.
5. Переход к новой текущей вершине. Выбираем из необозреваемых вершин вершину с наименьшей оценкой и делаем ее текущей. Если такая вершина не существует, то все вершины просмотрены и алгоритм заканчивает работу.
6. Восстановление кратчайшего пути. По окончании работы алгоритма, для каждой вершины можно восстановить кратчайший путь от начальной вершины до самой вершины.

Пример кода на языке C++

#include <iostream>
#include <vector>
#include <limits>

#define INF std::numeric_limits<int>::max()

void Dijkstra(std::vector<std::vector<int>>& graph, std::vector<int>& distances, int start) {
  int n = graph.size();
  std::vector<bool> visited(n, false);

  distances[start] = 0;

  for (int i = 0; i < n - 1; ++i) {
    int minDistance = INF;
    int minIndex = -1;

    // Выбираем вершину с наименьшей оценкой из необозреваемых вершин
    for (int j = 0; j < n; ++j) {
      if (!visited[j] && distances[j] < minDistance) {
        minDistance = distances[j];
        minIndex = j;
      }
    }

    if (minIndex == -1) {
      break; // Все вершины уже посещены
    }

    visited[minIndex] = true;

    // Пересчитываем оценки для соседних вершин
    for (int j = 0; j < n; ++j) {
      if (!visited[j] && graph[minIndex][j] != INF && distances[minIndex] + graph[minIndex][j] < distances[j]) {
        distances[j] = distances[minIndex] + graph[minIndex][j];
      }
    }
  }
}

int main() {
  int n, m, start;
  std::cin >> n >> m >> start;

  std::vector<std::vector<int>> graph(n, std::vector<int>(n, INF));
  std::vector<int> distances(n, INF);

  for (int i = 0; i < m; ++i) {
    int u, v, weight;
    std::cin >> u >> v >> weight;
    graph[u][v] = weight;
  }

  Dijkstra(graph, distances, start);

  std::cout << "Кратчайшие расстояния от вершины " << start << " до остальных вершин:\n";
  for (int i = 0; i < n; ++i) {
    std::cout << "Вершина " << i << ": " << distances[i] << "\n";
  }

  return 0;
}

В приведенном примере кода используется матрица смежности для представления графа. Ввод первой строки содержит количество вершин n, ребер m и вершину, от которой ищем кратчайший путь start. Затем следуют m строк, каждая из которых содержит информацию о ребре: начальную вершину, конечную вершину и вес ребра. После вызова функции Dijkstra расстояния до всех вершин выводятся на экран.

Алгоритм Дейкстры является одним из основных инструментов для решения задач на графах, связанных с нахождением кратчайшего пути. Его применение находит в таких областях, как маршрутизация в компьютерных сетях, оптимизация транспортных маршрутов, планирование производства и др. Он обладает хорошей временной сложностью O(n^2) для неориентированных графов и O(nlog(n)) для ориентированных графов с использованием минимальной кучи.