In a weighted graph G, the weight of a path is the sum of all edge...

  

Transcribed Image Text:

In a weighted graph G, the weight of a path is the sum of all edge weights in that path. Suppose we fix a vertex Vo. A minimal vo-spanning tree is a special spanning tree. Like all spanning trees there is a unique path from vo to any other vertex. But the special thing about this tree is that each of these paths is the shortest. The procedure to construct a minimal vå-spanning tree is called Dijkstra's Algorithm: 1. Start by defining a tree T (V, E) which contains only the vertex vo, i.e. V = {vo} and E = {}. 2. Consider all edges with one vertex in V and the other vertex not in V: N = {[v, u]: v € Vandu # V}. 3. Find the edge [u, v] E N which minimises the sum: vo, v + weight([v, u]). 4. Add u to V and add [u, v] to E. 5. Repeat steps 2, 3 and 4 until I is a spanning tree for G. When constructed in this way, (V, E) will be a minimal vo-spanning tree. Perform Dijkstra's algorithm on the following graph. Add/remove edges to the minimal vo-spanning tree by clicking on them. Edges in the tree will be coloured black. At each step the next edges to consider, N, will be coloured green. Each vertex in your tree will be automatically decorated with the weight of the path from vo to v along your tree. Correct application of the algorithm will ensure this number is minimal value Ivo, vl. Click "Submit Part" if you want information on your choices so far. ● 3 с 4 E AMA V0:0 3 А B 1 5 G 8 H 6 v1 In a weighted graph G, the weight of a path is the sum of all edge weights in that path. Suppose we fix a vertex Vo. A minimal vo-spanning tree is a special spanning tree. Like all spanning trees there is a unique path from vo to any other vertex. But the special thing about this tree is that each of these paths is the shortest. The procedure to construct a minimal vå-spanning tree is called Dijkstra's Algorithm: 1. Start by defining a tree T (V, E) which contains only the vertex vo, i.e. V = {vo} and E = {}. 2. Consider all edges with one vertex in V and the other vertex not in V: N = {[v, u]: v € Vandu # V}. 3. Find the edge [u, v] E N which minimises the sum: vo, v + weight([v, u]). 4. Add u to V and add [u, v] to E. 5. Repeat steps 2, 3 and 4 until I is a spanning tree for G. When constructed in this way, (V, E) will be a minimal vo-spanning tree. Perform Dijkstra's algorithm on the following graph. Add/remove edges to the minimal vo-spanning tree by clicking on them. Edges in the tree will be coloured black. At each step the next edges to consider, N, will be coloured green. Each vertex in your tree will be automatically decorated with the weight of the path from vo to v along your tree. Correct application of the algorithm will ensure this number is minimal value Ivo, vl. Click "Submit Part" if you want information on your choices so far. ● 3 с 4 E AMA V0:0 3 А B 1 5 G 8 H 6 v1