Алгоритм Дейкстры для своего графа
Состояние расчёта
Введите данные - результат обновится автоматически.
Путь найден
- Минимальная сумма весов
- 4
- Кратчайший путь
- 1 → 3 → 2 → 4
- Шагов выбора вершины
- 4
Часть значений появится, когда заполните остальные поля.
Расчёт справочный и не заменяет консультацию специалиста.
График платежейШаги алгоритма Дейкстры
Листайте таблицу по горизонтали
| Выбранная вершина | Расстояние от начала | Улучшенные расстояния |
|---|---|---|
| 1 | 0 | 2: ∞ → 4; 3: ∞ → 1 |
| 3 | 1 | 2: 4 → 3; 4: ∞ → 6 |
| 2 | 3 | 4: 6 → 4 |
| 4 | 4 | нет |
Вершины кратчайшего пути
Листайте таблицу по горизонтали
| Шаг пути | Вершина | Накопленный вес | Вес входящего ребра |
|---|---|---|---|
| 1 | 1 | 0 | старт |
| 2 | 3 | 1 | 1 |
| 3 | 2 | 3 | 2 |
| 4 | 4 | 4 | 1 |
Введите вершины и рёбра с неотрицательными весами. Калькулятор найдёт кратчайший путь, его вес и покажет шаги алгоритма или недостижимость.
Как считается
Состояние пути
TOOLS_DIJK(Рёбра,N,Тип,Старт,Финиш,0,0)Минимальная сумма весов
TOOLS_DIJK(Рёбра,N,Тип,Старт,Финиш,1,0)Кратчайший путь
TOOLS_DIJK(Рёбра,N,Тип,Старт,Финиш,2,0)Число показанных шагов
TOOLS_DIJK(Рёбра,N,Тип,Старт,Финиш,3,0)Число вершин пути
TOOLS_DIJK(Рёбра,N,Тип,Старт,Финиш,4,0)Пример расчёта
- N
- 4
- Тип
- Направленные
- Рёбра
- 1 2 4 1 3 1 3 2 2 2 4 1 3 4 5
- Старт
- 1
- Финиш
- 4
- Минимальная сумма весов
- 4
- Кратчайший путь
- 1 → 3 → 2 → 4
- Число показанных шагов
- 4
- Число вершин пути
- 4
Числа взяты из контрольного примера калькулятора - на них он проверяется тестами.
Источники
Комментарии (0)
Комментариев пока нет.
Оставить комментарий
Что посчитать?
Другие калькуляторы
Калькулятор резисторов
Калькулятор короба для сабвуфера
Калькулятор делителя напряжения на резисторах
Калькулятор параллельного соединения резисторов
Калькулятор резистора для светодиода
Калькулятор самозамеса
Листайте список вправо