1. We have discussed Dijkstra's algorithm in class for computing the shortest paths from any source node to all other nodes in a network. The first step is to codify the network information, i.e., how do we represent the link costs? One way is to use a matrix representation. If the link costs have been expressed as a matrix C, then the (i, j)th element of the matrix gives the cost of the link between i and j (obviously, if i = j, Cif = 0, for all i). For example, the cost matrix for the network shown in Fig. 1 is (first row/column is for node A, second row/column is for node B, etc.):
You can assume that the user would not make any error in entering the link cost matrix (i.e., the matrix would be symmetric, non-negative, and al elements along the leading diagonal will be 0). That is, your code does not need to check for potential errors in the link cost matrix.
Write a function computeDijkstra(sourceID,C)' which takes as inputs the source node ID and the link cost matrix and returns the final best cost vector and the final predecessor vector.
For example, referring to slide-38 of Chapter-5 notes, your out¬put arguments should be [0,2,3,1,2,4] and [A, A, E, A, D, El or [1,1,5,1,4,5] if you label each node by a numeric, i.e., [A, B, C, D, E] -4 [1,2,3,4,5].
The pseudocode is available on slide-36 of Chapter-5 notes.
If you cannot implement the predecessor vector, just try to return the final cost vector. You can earn up to 50 points if you do so correctly.
You cannot use built in functions which directly compute the shortest path tree or implement Dijkstra's algorithm.
Here's a MATLAB tip. Suppose x = [2, 3, 1, 4, 5]. Executing (a,b) = min(x) returns a=1 and b=3. The parameter b therefore returns the position in x where the minimum is found.
Figure 1: Network for Problem 1.
NOTE: You should email me your codes with instructions on how to rim than.