Кратчайший путь в графе: алгоритм Дейкстры онлайн

Находит кратчайший путь между двумя вершинами взвешенного графа по списку рёбер: длина пути, последовательность вершин. Ориентированный или неориентированный граф.

Данные

Встроить калькулятор на свой сайт

Скопируйте код и вставьте на страницу — калькулятор будет работать внутри вашего сайта. Ссылка на источник уже включена в виджет.

<iframe src="https://itcalcs.ru/embed/kratchajshij-put-v-grafe/" width="100%" height="560" style="border:0;max-width:760px" loading="lazy" title="Кратчайший путь в графе: алгоритм Дейкстры онлайн"></iframe>

8длина путикратчайший путь A → D в примере

3ребра в путиA → C → B → D

5рёбер на входеграф из примера

≥ 0вес ребратребование алгоритма Дейкстры

Что такое кратчайший путь в графе

Кратчайший путь в графе — это маршрут между двумя вершинами с минимальной суммой весов рёбер. Калькулятор принимает список рёбер, находит оптимальный путь алгоритмом Дейкстры и показывает его длину и порядок вершин.

Список рёбер на входе

Каждая строка записывается как «вершина вершина вес»: например, A B 4. Имена вершин могут быть любыми словами без пробелов.

Направленный или нет

Для неориентированного графа ребро работает в обе стороны, для ориентированного только от первой вершины ко второй.

Результат с маршрутом

Вы получаете не только число, но и последовательность вершин, а также количество рёбер в пути.

Как работает алгоритм Дейкстры

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

Шаги алгоритма

Стартовой вершине присваивается расстояние 0, остальным бесконечность. На каждом шаге берётся ближайшая непосещённая вершина и обновляются расстояния до её соседей.

d(v) = min( d(v), d(u) + w(u, v) )

d — текущее расстояние от старта, u — выбранная вершина, w(u, v) — вес ребра между u и v.

Только неотрицательные веса При отрицательном весе жадный выбор ближайшей вершины перестаёт гарантировать верный ответ. Для таких графов используют алгоритм Беллмана — Форда.

Пример из калькулятора Путь A → C → B → D даёт 2 + 1 + 5 = 8, а прямой путь A → C → D стоил бы 2 + 8 = 10, то есть длиннее.

Для чего нужен поиск кратчайшего пути

Задача возникает везде, где нужно выбрать самый дешёвый или быстрый маршрут по сети.

Маршруты и логистика

Вершины — это города или склады, веса — расстояния или время. Результат показывает оптимальную цепочку пунктов.

Сети и связь

В компьютерных сетях веса обозначают задержку или стоимость канала, а путь определяет, как пойдёт пакет.

Учёба и олимпиады

Калькулятор помогает проверить ручное решение задачи по теории графов или разобрать шаги алгоритма.

Игры и карты

Поиск пути на карте с клетками разной проходимости сводится к графу с весами.

Как читать результат

Сопоставьте длину пути и число рёбер: они говорят о разных вещах.

Путь не найден

Вершины не связаны: между ними нет цепочки рёбер.
Проверьте направление рёбер и написание имён вершин.
Добавьте недостающие рёбра или переключите тип графа.

Обычный результат

Длина пути конечна, вершины идут в логичном порядке.
Сверьте ответ с рисунком графа, если он у вас есть.
Проверьте, что сумма весов вдоль пути совпадает с ответом.

Очень длинный путь

Длина пути заметно больше весов отдельных рёбер: маршрут идёт в обход.
Проверьте, нет ли пропущенного прямого ребра.
Возможно, граф ориентированный, а нужны двусторонние связи.

Советы по вводу графа

Аккуратный ввод экономит время при разборе результатов.

Один формат записи

Пишите ребро на новой строке и разделяйте элементы пробелом, без запятых и скобок.

Проверяйте регистр имён

Вершины A и a считаются разными, поэтому единообразно называйте одну и ту же вершину.

Различайте тип графа

Если дороги двусторонние, оставляйте граф неориентированным. Для односторонних связей включайте ориентированный режим.

Не используйте отрицательные веса

Алгоритм Дейкстры для них не подходит; при необходимости сначала пересчитайте веса или выберите другой метод.

Кратчайший путь в графе: алгоритм Дейкстры онлайн онлайн

Находит кратчайший путь между двумя вершинами взвешенного графа по списку рёбер: длина пути, последовательность вершин. Ориентированный или неориентированный граф. Калькулятор доступен бесплатно, работает на компьютере и телефоне и подходит для быстрой проверки расчётов.

Как пользоваться калькулятором «кратчайший путь в графе»

Введите «Рёбра: вершина вершина вес, по строке».
Введите «Откуда».
Введите «Куда».
При необходимости включите «Ориентированный граф».
Результат появится справа мгновенно — нажимать кнопку «Рассчитать» не нужно.

Пример расчёта

Если рёбра: вершина вершина вес, по строке — A B 4 A C 2 C B 1 B D 5 C D 8; откуда — A; куда — D; ориентированный граф — нет, то результат: длина кратчайшего пути: 8; путь: A → C → B → D; рёбер в пути: 3.

Частые вопросы

Для чего нужен алгоритм Дейкстры?

Для поиска кратчайших маршрутов в навигации, компьютерных сетях и логистике.

Работает ли он с отрицательными весами?

Нет, при отрицательных рёбрах результат может быть неверным, нужен алгоритм Беллмана — Форда.

Чем отличается ориентированный граф?

Рёбра проходятся только в указанном направлении: от первой вершины ко второй.

Как найти кратчайший путь в графе вручную?

Присвойте старту расстояние 0, остальным бесконечность, затем всегда берите ближайшую непосещённую вершину и обновляйте расстояния до её соседей. Когда достигнута целевая вершина, путь восстанавливают в обратном порядке по предшественникам.

Можно ли применять Дейкстру для отрицательных рёбер?

Нет, алгоритм Дейкстры требует неотрицательных весов. При отрицательном ребре расстояние до уже обработанной вершины может уменьшиться, а алгоритм этого не учтёт. В таких случаях используют алгоритм Беллмана — Форда.

Чем отличается ориентированный граф от неориентированного?

В ориентированном графе ребро проходится только от первой вершины ко второй, в неориентированном в обе стороны. Из-за этого кратчайший путь туда и обратно в ориентированном графе может различаться или не существовать.

Что значит число рёбер в пути?

Это количество переходов между вершинами вдоль найденного маршрута. Оно отличается от длины пути: длина суммирует веса, а число рёбер просто считает шаги. В примере три ребра при длине 8.

Сколько вершин выдержит калькулятор?

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

Может ли быть несколько кратчайших путей?

Да, если два маршрута имеют одинаковую минимальную сумму весов. Калькулятор показывает один из них. Если нужен весь список, проверьте варианты вручную или измените веса, чтобы выяснить различия.

Как пользоваться калькулятором «кратчайший путь в графе»?

Заполните поля формы — результат рассчитывается автоматически и обновляется при каждом изменении значений. Можно скопировать результат, распечатать страницу или отправить ссылку с вашими данными.

По какой формуле считает калькулятор «кратчайший путь в графе: алгоритм Дейкстры онлайн»?

Алгоритм Дейкстры шаг за шагом выбирает ближайшую непосещённую вершину и обновляет расстояния до её соседей. Работает только при неотрицательных весах рёбер.

Нужно ли регистрироваться и платить?

Нет. Калькулятор бесплатный и работает без регистрации. Введённые данные обрабатываются в вашем браузере и никуда не отправляются.

Теги:#алгоритм дейкстры онлайн#кратчайший путь в графе#поиск кратчайшего пути калькулятор#теория графов калькулятор#алгоритм дейкстры пример#поиск пути в графе онлайн#как найти кратчайший путь между вершинами#кратчайший путь в взвешенном графе#дейкстра калькулятор онлайн#задача о кратчайшем пути#ориентированный граф кратчайший путь

Страница обновлена: 01.11.2026. Формулы и значения проверяются при каждом обновлении каталога.