The diagram below shows an undirected graph. We would like to investigate the effect of negative...

Transcribed Image Text:

The diagram below shows an undirected graph. We would like to investigate the effect of negative edge weights when using Dijkstra's algorithm to find the lowest cost path from A to all other nodes. A W₁ W₂ B с W3 WA Produce two versions of this graph with edge weights to show: (a) One example where the presence of a negative weighted edge causes an incorrect path cost to be calculated by the Dijkstra algorithm for one or more of the graph nodes. You answer should make clear which path cost(s) is incorrect. (b) One example where the correct path costs are calculated for all nodes even though one of the edges is negative weighted. Note: Both graphs must be fully labelled with edge weights such that w; > 0 in your both examples. Please fill the blanks in your answer sheet. You should then provide a short explanation as to why one of the graphs gave rise to a correct result and why one gave rise to an incorrect result. You answer should refer to the concept of an invariant. The diagram below shows an undirected graph. We would like to investigate the effect of negative edge weights when using Dijkstra's algorithm to find the lowest cost path from A to all other nodes. A W₁ W₂ B с W3 WA Produce two versions of this graph with edge weights to show: (a) One example where the presence of a negative weighted edge causes an incorrect path cost to be calculated by the Dijkstra algorithm for one or more of the graph nodes. You answer should make clear which path cost(s) is incorrect. (b) One example where the correct path costs are calculated for all nodes even though one of the edges is negative weighted. Note: Both graphs must be fully labelled with edge weights such that w; > 0 in your both examples. Please fill the blanks in your answer sheet. You should then provide a short explanation as to why one of the graphs gave rise to a correct result and why one gave rise to an incorrect result. You answer should refer to the concept of an invariant.

Answer rating: 100% (QA)

a Let w13 w21 w32 and w41 Applying the Dijkstras algorihm we get the following The path ... View the full answer