Дано: ориентированный граф 𝐺 = (𝑉, 𝐸),𝑉 = (𝑠, 𝑎, 𝑏, 𝑐, 𝑑, 𝑒,𝑡), 𝐸 = = (𝑒1, … , 𝑒10), вес любого ребра ∈ [1; 15]. Найти кратчайший путь из s в t с помощью соответствующего алгоритма. (Решение → 16300)

Заказ №38675

Дано: ориентированный граф 𝐺 = (𝑉, 𝐸),𝑉 = (𝑠, 𝑎, 𝑏, 𝑐, 𝑑, 𝑒,𝑡), 𝐸 = = (𝑒1, … , 𝑒10), вес любого ребра ∈ [1; 15]. Найти кратчайший путь из s в t с помощью соответствующего алгоритма. В условии должно быть несколько возможных путей из s в t.

Решение.

0,1, 2,3,4, 5, 6 – Соответственно a,b,c,d,e,t,s. Окрашиваем вершину s, полагаем, что 𝑑(𝑠) = 0, 𝑑(𝑥) = ∞ для любого 𝑥 ≠ 𝑠 и что 𝑦 = 𝑠. Имеем 𝑑(𝑎) = 8; 𝑑(𝑏) = min{∞; 0 + ∞} = ∞; 𝑑(𝑐) = min{∞; 0 + 6} = 6; 𝑑(𝑑) = min{∞; 0 + 13} = 13; 𝑑(𝑡) = min{∞; 0 + 15} = 15; 𝑑(𝑒) = min{∞; 0 + 10} = 10.