The highway distance between 7 cities named (A ... G) are shown in the figure below:

a)Does this graph possess a Euler path or Euler circuit? why? (4 marks)

b)List the right sequence of nodes traversed by the DFS and BFS algorithm starting from node

A.(4 marks)

B.

c)Draw the minimum spanning tree of this graph (3 marks).

d)Use the Dijkstra's algorithm to determine the shortest paths from city (A) to all other cities (6 marks). Determine the shortest path and cost from node A to node D (2 marks).

[Hint: implement the algorithm step by step to show which node will be added in sequence]

e)Determine the shortest paths between all pairs of nodes. (16 marks)