Кратчайшие пути в графах

Граф представляет собой математическую структуру, состоящую из множества вершин (узлов) и множества рёбер (связей между вершинами).

Граф обозначается как $(V,E)$, где $V$ – множество вершин, $E$ – множество рёбер.

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

$$\text{Пусть } d(v_i) \text{ - минимальное расстояние до вершины } v_i.$$

$$d(v_i) = \min \{d(v_j) + w_{ij} | v_j \in N(v_i)\}$$

где $w_{ij}$ – вес ребра между вершинами $v_i$ и $v_j$.

Рассмотрим граф с вершинами $A,B,C,D$ и рёбрами с весами:

`` A -> B: 7 A -> C: 9 B -> C: 10 B -> D: 14 C -> D: 2 D -> A: 9 ``

Начальная вершина $A$. Применим алгоритм Дейкстры:

В результате получаем кратчайшие пути от вершины $A$ до всех других вершин.