Dijkstra’s algorithm on Matlab
Homework
In this project, students are required to design a program to perform Dijkstra’s algorithm on Matlab. Specifically, consider 400 points in the 2D plane, where the coordinate of each point is (?,?) with ? = 1,2,3,...,20 and ? = 1,2,3,...,20. In other words, the coordinates of these 400 points are respectively listed as
(1,1), (1,2), (1,3), ... , (1,20), (2,1), (2,2), (2,3), ... , (2,20),
...
(20,1), (20,2), (20,3), ... (20,20).
Then, keep two points (1,1) and (20,20), and randomly remove 120 points from the other 398 points. One way to do this is as follows. First, you label these 398 points, e.g., the index of (1,2) is 1, that of (1,3) is 2, ..., that of (20,19) is 398. Then, you use Matlab to randomly generate 120 different indices from 1 to 398, with the command “randperm”. Last, you remove the points corresponding to these 120 indices. Among these 280 remaining points, the distance between two points (?1, ?1) and (?2, ?2) is
√(?1 −?2) +(?1 −?2) .
Step 1: Building the graph. Please build a graph ? = (?, ?) on Matlab based on the following requirements.
1.1 In this graph, the set of nodes ? consists of all the remaining 280 points. 1.2Foranytwonodes (?1,?1) and (?2,?2) onthisgraph,thereisanedgetoconnect themifandonlyif ‖?1 −?2‖≤1 and ‖?1 −?2‖≤1.Forexample,thenode (2,2) is only connected to (1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), and (3,3), if all the above nodes are among the 280 remaining points.
1.3 If there is an edge to connect two nodes (?1,?1) and (?2,?2) on this graph, the cost associated with this edge is the distance between these two nodes, i.e.,
22 √(?1 −?2) +(?1 −?2) .
Step 2: Finding the least cost path on graph. Please design a program on Matlab, where you use the Dijkstra’s algorithm shown in Lecture 4 to find the least cost path from node (1,1) to node (20,20) on the graph built in Step 1. Note that on Matlab, there is a package that can run the shortest path algorithm. Do not use the built-in package in Matlab. Design your own program using the knowledge in Lecture 4.
Requirements: Every time when you randomly remove 120 points among the 398
points, you can build a graph based on the method in Step 1. Please generate 5 different graphs, each with 120 random points removed from 398 points. For each graph, show inafiguretheleastcostpathfrom (1,1) to (20,20) basedontheDijkstra’salgorithm that you designed on Matlab. For example, you can follow the format in the figure below to demonstrate your results.
Figure 1: An example to show the least cost path
In Figure 1, there are 400 points. In particular, the red points are the 120 randomly selected points that are removed, and the green points are the 280 remaining nodes on thegraph.Underthissetup,theleastcostpathfrom (1,1) to (20,20) isshownbythe line connecting these two nodes.
Notethatsometimes,thereisnofeasiblepathfrom (1,1) to (20,20) ontherandomly generated graph, as shown in the example below.
Figure 2: An example without a feasible path
In Figure 2, there is no edge to connect the node (20,20) to any other node, because its three neighbors are removed. Therefore, there is no path to reach node (20,20). In this case, you just need to keep re-generating the graphs until you get 5 graphs each with a feasible path to connect (1,1) and (20,20).
Submission Checklist:
- Your Matlab code
- A report in pdf format covering
2.1 Your name and student ID
2.2 Five figures as described in Requirements.
