Reference no: EM131636806

Question: Give an example to show that Dijkstra's algorithm does not work when negative weights are allowed. Another algorithm for finding shortest paths from a single source node to all other nodes in the graph is the Bellman-Ford algorithm. In contrast to Dijkstra's algorithm, which keeps a set of nodes whose shortest path (minimum-weight path) of whatever length (that is, number of hops) has been determined, the Bellman-Ford algorithm performs a series of computations that seeks to find successively smaller-weight paths of length 1, then of length 2, then of length 3, and so on, up to a maximum of length n - 1 (if a path exists at all, then there is a path of length no greater than n - 1). A pseudocode description of the Bellman-Ford algorithm is given in the accompanying box; when using this algorithm, the adjacency matrix A must have a3 i, i4 = 0 for all i.