A puzzle has multiple ways of reaching the end solution. Fig. 1 shows a graph that represents all possible routes to the solution. The starting point of the game is represented by A, the solution is represented by S. The other points in the graph are possible intermediary stages

 

A puzzle has multiple ways of reaching the end solution. Fig. 1 shows a graph that represents all possible routes to the solution. The starting point of the game is represented by A, the solution is represented by S. The other points in the graph are possible intermediary stages

(a) The graph in Fig. 1 is a visualization of the problem.

(i) Identify the differences between a graph and a tree. [0-5]

A graph is a set of vertices, nodes and edges where there is no unique node which is known as root while a tree is a set of nodes and edges where there is a unique node which is known as root.

(ii) Explain in detail how the graph is an abstraction of the problem. [0-5]

The graph is an abstraction of the problem because it entails choosing and analyzing an action at a series of smaller steps to move closer to the goal. The graph represents a puzzle with multiple ways of reaching the end solution

(iii) Identify the advantages of using a visualization such as the one shown in Fig. 1. [0-5]

One of the advantages of using a visualization such as the one shown in Fig is because the graph can be used to represents a puzzle with multiple ways of reaching the end solution. The visualization entails the collection of data nodes or vertices where the Connections / edges are set between nodes or vertices. Graphs (edges) can also be directional or bi-directional and they can be directed or undirected.

 

(b) Demonstrate how Dijkstra’s algorithm would find the shortest path to the solution in Fig.1 through diagrams and written explanation of each stage. [0-25]

Dijkstra’s shortest path algorithm is designed to find the shortest path from source to every other node in a weighted graph. It can be used to find the shortest path to the solution in Fig.1 through the following steps:

·                     Mark A as the initial node and then visit B (5)

·                     Node E (8) is then visited (chosen from C (13), D (14), E (8))

·                     Node I (12) is then visited after E

·                     Node J (14) is then visited after I

·                     Visiting G (15) from C - overriding the previous value of 18

·                     Solution A-B-E-I-J path length 14