(c) In a shortest path problem, if each arc length increases by K units, shortest path...

Transcribed Image Text:

(c) In a shortest path problem, if each arc length increases by K units, shortest path distances increases by a multiple of K. (d) In a shortest path problem, if each arc length decreases by K units, shortest path distances decreases by a multiple of K. (e) Among the shortest paths in a network, Dijkstra's algorithm always finds a shortest path with the least number of arcs. (II) Suppose that all arcs in a network G have length one. Show that the Dijkstra's algorithm examines nodes for this network in the same order as the breadth-first search algorithm. (c) In a shortest path problem, if each arc length increases by K units, shortest path distances increases by a multiple of K. (d) In a shortest path problem, if each arc length decreases by K units, shortest path distances decreases by a multiple of K. (e) Among the shortest paths in a network, Dijkstra's algorithm always finds a shortest path with the least number of arcs. (II) Suppose that all arcs in a network G have length one. Show that the Dijkstra's algorithm examines nodes for this network in the same order as the breadth-first search algorithm.