设无向图G=(y,E),其中y={l,2,3,4,5},E={(1,2,4),(2,5,5),(1,3,2),(2,4,4),(3,4,1),(4,5,3),(1,5,8)},每条边由一个三元组表示,三元组中前两个元素为与该边关联的顶点,第三个元素为该边的权.请写出图G中从顶点1到

Question

设无向图G=(y,E),其中y={l,2,3,4,5},E= {(1,2,4),(2,5,5),(1,3,2),(2,4,4),(3,4,1),(4,5,3),(1,5,8)},每条边由一个三元组表示,三元组中前两个元素为与该边关联的顶点,第三个元素为该边的权.请写出图G中从顶点1到其余各点的最短路径的求解过程.要求列出最短路径上的各顶点,并计算路径长度

Answer 1

最坏情况:初始状态反序,则需要进行n-1趟扫描,每趟扫描要进行n-i次关键字的比较,且每次需移动记录3次