Solution for HW 4, CS 3114, Summer 2016 ------------------------------------------------------------------------------------ Q1: a b c d e f g h i j k node added / distance -------------------------------------------------------------------------------- 0 x x x x x x x x x x add 6* x x 5* x x 8* x x x a / 0 6 x x add 8* x 6* x x x e / 5 add x x 7* x 6 x x x b / 6 9* x 7 x add 9* x x h / 6 8* 13* add 14* 9 10* x f / 7 add 10* 14 9 10 x c / 8 10 14 add 10 x i / 9 add 12* 10 16* d / 10 11* add 14* j / 10 add 14 g / 11 add k / 14 -------------------------------------------------------------------------------- Q2: Pass 1: a --> b --> c --> d --> k <-- add k <-- add d c --> g <-- add g <-- add c <-- add b a --> e <-- add e done add a Pass 2: f add f Pass 3: h --> i --> j <-- add j <-- add i done add h Ordering from first-done to last-done: h, i, j, f, a, e, b, c, g, d, k