Pseudo Code
Урок 4 из 9 курса Алгоритм Дейкстры — Алгоритмы на графах на Coddy.
dijkstra(n, edges, source):
dist = [INF, INF, ...]; dist[source] = 0
visited = all false
repeat n times:
u = unvisited vertex with smallest dist (none reachable -> stop)
visited[u] = true
for each edge (a -> b, weight w):
if a == u and dist[u] + w < dist[b]:
dist[b] = dist[u] + w
replace every remaining INF with -1
return dist- INF — это просто число, которое больше любого реального расстояния (например, 1000000000).
- Выбор непосещённой вершины с наименьшим значением dist в каждом раунде — это жадная суть алгоритма Дейкстры. Сканирование плоского списка рёбер для релаксации делает код простым и работает на любом языке.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Алгоритм Дейкстры — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity