Given a weighted graph G in adjacency-list representation G = { 0:{1:5, 4:9, 7:8

Question

Given a weighted graph G in adjacency-list representation G = { 0:{1:5, 4:9, 7:8}, 1:{2:12, 3:15, 7:4}, 2:{3:3, 6:11}, 3:{6:9}, 4:{5:4, 6:20, 7:5}, 5:{2:1, 6:13}, 7: {5:6, 2:7} }, where, for example 3:{6:9} means that the node 3 is connected only to the node 6 with an edge of weight 9. a) Run the Dijkstra algorithm. What will be the content of the queue after 5 iterations? b) Run Bellman-Ford algorithm. What edges will be in the shortest-path tree? In both cases a) and b) consider that the source s is the node 0.

Explanation / Answer

a) After running the dijkstra's algorithm,
    Node            Shortest path                  Predecessor
     0                      0                                   null
     1                      5                                    0
     7                      8                                    0
     4                      9                                    0
     5                      13                                  4
     2                      14                                  5
     3                      17                                  2
     6                      26                                  5
Queue content after 5 iterations:   2, 3 and 6

b) Edges that will be in the shortest path tree:
   0->1, 0->4, 0->7, 4->5, 5->2, 2->3, 5->6

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.