Графы: матрица и кратчайший путь
Задайте граф матрицей смежности — увидите его рисунок и найдёте кратчайший путь между вершинами (алгоритм Дейкстры). Как в задании на таблицы расстояний ЕГЭ. Считается прямо в браузере.
Вершин:
Матрица смежности (вес ребра, 0 — нет ребра)
| А | Б | В | Г | Д | |
|---|---|---|---|---|---|
| А | — | ||||
| Б | — | ||||
| В | — | ||||
| Г | — | ||||
| Д | — |
Граф · путь →
Готовим граф…
Кратчайший путь А → Д: А → В → Д = 9
О графах и кратчайшем пути
Граф — это вершины и связывающие их рёбра (с весами — «длинами»). Матрица смежности хранит вес ребра между каждой парой вершин. Алгоритм Дейкстры находит кратчайшие расстояния от выбранной вершины до остальных, всегда расширяя ближайшую ещё не обработанную. Здесь граф неориентированный: изменение веса A→B автоматически задаёт B→A.
