StudyDocs.ru Logo

Лабораторная работа4.docx


Лабораторная работа №4 Апухтин Михаил группа А-13-08
Рёбра имеют длины w(e)=i+j (mod 10)I этапV=V1Г(V)={V4,V5,V6,V7}e(V4)=min{,0+5}=5e(V5)=min{,0+6}=6e(V6)=min{∞,0+7}=7e(V7)=min{∞,0+8}=8V=V4Г(V)={V1,V2,V3,V7}e(V2)=min{∞,5+6}=11e(V3)=min{∞,5+7}=12e(V7)=min{8,5+1}=6Длина минимального пути=6II этапL=[V7] V=V7Г-(V)={V1,V2,V3,V4}e*(V)=e*(U)+w(U,V)6=5+1 при U=V4L=[V4,V7] V=V4Г-(V)={V1,V2,V3,V7}e*(V)=e*(U)+w(U,V)5=0+5 при U=V1L=[V1,V4,V7] – минимальный путь из V1 в V7