Решить задачу о кратчайшем пути в сети. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по логистике
Решить задачу о кратчайшем пути в сети

Решить задачу о кратчайшем пути в сети .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Решить задачу о кратчайшем пути в сети. Построить математическую модель задачи Найти решение в МS Excel xi,xj 1,2 1,3 1,4 2,5 3,5 3,4 4,5 4,6 5,7 6,7 lij 7 8 5 12 8 9 7 13 9 6

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Построим граф
Найдем кратчайшие расстояния в сети с помощью алгоритма Дейкстры
Полагаем: d1=0* d2=d3=d4=d5=d6=d7=∞
1 итерация: текущая вершина с постоянной меткой y= 0, далее расставляем метки у вершин, достижимых из 1
d2=7(1)
d(3)=8(1)
d4=min0+5, 8+9 =5*(1)
Звездочкой отмечена наименьшая метка из чисел 7,8,5. При этом данная метка будет постоянной (в нашем случае у вершины 4 постоянная метка).
2 итерация: текущая вершина с постоянной меткой y =4 , далее меняем метки у вершин с временными метками (меняются лишь метки тех вершин, которые достижимы из вершины 4)
d5=min7+12, 8+8, 5+7=12*(4)
d6=5+13=18(4)
d2=7(1)
d3=8(1)
d7=∞
3 итерация: текущая вершина с постоянной меткой y=2
4 итерация: текущая вершина с постоянной меткой y=3
5 итерация: текущая вершина с постоянной меткой y=2
d7=min⁡(12+9, 18+6)= 21*(5)
4 итерация: текущая вершина с постоянной меткой y=4
d5=min7+12, 8+8, 5+7 =12(4)
d6=5+13 =18*(4)
5 итерация: текущая вершина с постоянной меткой y=5
d7=min⁡(12+9, 18+6)= 21*(5)
Вершина 7 имеет постоянную метку, следовательно 21 – длина кратчайшего пути от 1 до 7

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу