Shortest Even Walk and Shortest Path Tree in Graphs

Problem 1: Shortest Even Walk

Problem 1(Shortest Even Walk).Design an algorithm to find the length of the shortestwalk1containing an even number of edges from a source vertexsto a destination vertextin adirected graph with non-negative edge lengths`(u, v). Your algorithm should run inO(m+nlogn)time.As described in lecture for Dijkstra’s algorithm, you can assume that there is a data structureQthat stores vertices with a functiond(·) defined on them, while supporting the following operations:(a) updates of the formd(v) := min(d(v), d(u) +`(u, v)) inO(1) time, and(b) extracting the vertex with the smallest value ofd(v), i.e.,vmin:= arg minv∈Qd(v) fromQinO(logn) time.Problem 2(Shortest Paths and Minimum Spanning Trees) A shortest path tree of agraph is defined as a rooted tree such that the unique path from the root to every other vertex inthe tree is a shortest path in the graph between those two vertices.

(a) Show that for any undirected graph (with nonnegative edge weights) and any vertexin it designated as the root vertex, there always exists a shortest path tree rooted at that vertex.

(b) Give an example of an undirected graph (with nonnegative edge weights) and ashortest path tree that is not a minimum spanning tree of the graph