adjacency matrix: A B C D E F A 0 7 19 28 B 7 0 10 18 40 C 19 10 0 16 17 D 18 16 0 14 10 E 40 14 0 12 F 28 17 10 12 a) Draw the graph that represent such adjacency matrix b) List the right sequence of nodes traversed by the DFS and BFS algorithm starting from node A. c) Does this graph possess a Euler circuit/path? , why? If any of them does not exist, how the graph can be modified to have one? d) Draw the minimum spanning tree of this graph . e) Use the Dijkstra's algorithm to determine the shortest paths from city (A) to all other cities . Determine the shortest path and cost from node A to node E . [Hint: implement the algorithm step by step to show which node will be added in sequence] f) Determine the shortest paths between all pairs of nodes using Floyd-Warshall algorithm.
The highway distance between 6 cities named (A ... G) are illustrated in the following
adjacency matrix:
A B C D E F
A 0 7 19 28
B 7 0 10 18 40
C 19 10 0 16 17
D 18 16 0 14 10
E 40 14 0 12
F 28 17 10 12
a) Draw the graph that represent such adjacency matrix
b) List the right sequence of nodes traversed by the DFS and BFS
node A.
c) Does this graph possess a Euler circuit/path? , why? If any of them
does not exist, how the graph can be modified to have one?
d) Draw the minimum spanning tree of this graph .
e) Use the Dijkstra's algorithm to determine the shortest paths from city (A) to all other
cities . Determine the shortest path and cost from node A to node E .
[Hint: implement the algorithm step by step to show which node will be added in
sequence]
f) Determine the shortest paths between all pairs of nodes using Floyd-Warshall
algorithm.
Step by step
Solved in 2 steps with 5 images
