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

1.

2.

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

3.

Задача алгоритма
Нахождение наилучшего маршрута между двумя
европейскими городами Рейкьявиком и Белградом.
Обратите внимание на следующее:
Каждый город — это узел.
Каждая дорога — это ребро.
У каждой дороги есть своя ценность. Это может
быть расстояние между городами, плата за проезд
или интенсивностью движения.

4.

5.

6.

7.

8.

Шаги/
Вершины
Reykjavik
Olso
London
Berlin
Moscow
Rome
Belgrade
Athens
1
0
∞
∞
∞
∞
∞
∞
∞
2
∞
5
4
∞
∞
∞
∞
∞
3
∞
∞
∞
7
∞
∞
∞
∞
4
∞
∞
∞
6
8
∞
∞
∞
5
∞
∞
∞
∞
∞
8
15
∞

9.

Цифровые картографические
услуги в Картах Google.
IP-маршрутизация для поиска
кратчайшего пути