Pull to refresh
27
0
Алексей Сплитфейс @splitface

User

Send message

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

Reading time 3 min
Views 430K
Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

image

Читать дальше →
Total votes 91: ↑62 and ↓29 +33
Comments 31

Information

Rating
Does not participate
Location
Киев, Киевская обл., Украина
Registered
Activity