Библиотека Возможности Предметы Вопросы Войти Начать

Для чайников

dlyachainikov.ru

Сессия для чайников — разберёмся вместе

Политика конфиденциальности Пользовательское соглашение Контакты

Шпаргалка — Для чайников

Войти Начать

К конспекту

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

dlyachainikov.ru · Дискретная математика

Основные понятия

Граф обозначается как $(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$ . Применим алгоритм Дейкстры:
Начальное состояние: $d(A)=0$ , $d(B)=\infty$

Пропуски

граф
алгоритм
вес
обход
кратчайший
соседняя

.

,

d(C)=\infty

,

V

Текущая вершина

A

, обновляем

d(B)

и

d(C)

Текущая вершина

B

, обновляем

d(C)

и

d(D)

Текущая вершина

C

, обновляем

d(D)