Найдите кратчайшие пути между вершиной 1 и всеми остальными

Question

Вопрос:

Найдите кратчайшие пути между вершиной 1 и всеми остальными

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Краткое пояснение:

Метод: Для нахождения кратчайших путей в графе с отрицательными весами, но без отрицательных циклов, используется алгоритм Беллмана-Форда. В данном случае, поскольку есть отрицательный вес (-4) и граф не содержит отрицательных циклов, этот алгоритм подходит. Если бы все веса были неотрицательными, можно было бы использовать алгоритм Дейкстры.

Алгоритм Беллмана-Форда:

Алгоритм работает в $$V-1$$ итераций, где $$V$$ — количество вершин. На каждой итерации мы пытаемся релаксировать все ребра. Если после $$V-1$$ итераций мы можем релаксировать какое-либо ребро, это означает наличие отрицательного цикла.

Граф:

Вершины: 1, 2, 3, 4, 5, 6, 7, 8, 9
Ребра и веса: (1,2):10, (1,3):6, (1,4):8, (2,4):5, (2,7):11, (3,4):2, (3,5):3, (4,5):5, (4,6):7, (4,7):12, (5,6):9, (5,9):12, (6,8):8, (6,9):10, (7,8):6, (8,9):15, (1,5):-4

Инициализация:

Расстояние от вершины 1 до самой себя = 0.
Расстояние от вершины 1 до всех остальных вершин = ∞.

Итерации:

Итерация 1:

(1,2): dist[2] = min(∞, 0+10) = 10
(1,3): dist[3] = min(∞, 0+6) = 6
(1,4): dist[4] = min(∞, 0+8) = 8
(1,5): dist[5] = min(∞, 0+(-4)) = -4
(2,4): dist[4] = min(8, 10+5) = 8
(2,7): dist[7] = min(∞, 10+11) = 21
(3,4): dist[4] = min(8, 6+2) = 8
(3,5): dist[5] = min(-4, 6+3) = -4
(4,5): dist[5] = min(-4, 8+5) = -4
(4,6): dist[6] = min(∞, 8+7) = 15
(4,7): dist[7] = min(21, 8+12) = 21
(5,6): dist[6] = min(15, -4+9) = 5
(5,9): dist[9] = min(∞, -4+12) = 8
(6,8): dist[8] = min(∞, 5+8) = 13
(6,9): dist[9] = min(8, 5+10) = 8
(7,8): dist[8] = min(13, 21+6) = 13
(8,9): dist[9] = min(8, 13+15) = 8

Расстояния после итерации 1: {1:0, 2:10, 3:6, 4:8, 5:-4, 6:5, 7:21, 8:13, 9:8}

Итерация 2:

(1,2): dist[2] = 10
(1,3): dist[3] = 6
(1,4): dist[4] = 8
(1,5): dist[5] = -4
(2,4): dist[4] = min(8, 10+5) = 8
(2,7): dist[7] = min(21, 10+11) = 21
(3,4): dist[4] = min(8, 6+2) = 8
(3,5): dist[5] = min(-4, 6+3) = -4
(4,5): dist[5] = min(-4, 8+5) = -4
(4,6): dist[6] = min(5, 8+7) = 5
(4,7): dist[7] = min(21, 8+12) = 21
(5,6): dist[6] = min(5, -4+9) = 5
(5,9): dist[9] = min(8, -4+12) = 8
(6,8): dist[8] = min(13, 5+8) = 13
(6,9): dist[9] = min(8, 5+10) = 8
(7,8): dist[8] = min(13, 21+6) = 13
(8,9): dist[9] = min(8, 13+15) = 8

Расстояния после итерации 2: {1:0, 2:10, 3:6, 4:8, 5:-4, 6:5, 7:21, 8:13, 9:8}

Расстояния не изменились, значит, мы нашли кратчайшие пути.

Кратчайшие пути от вершины 1:

Вершина 1: 0
Вершина 2: 10 (1 -> 2)
Вершина 3: 6 (1 -> 3)
Вершина 4: 8 (1 -> 4)
Вершина 5: -4 (1 -> 5)
Вершина 6: 5 (1 -> 5 -> 6)
Вершина 7: 21 (1 -> 2 -> 7)
Вершина 8: 13 (1 -> 5 -> 6 -> 8)
Вершина 9: 8 (1 -> 5 -> 9)