//DO NOT CHANGE ANY EXISTING CODE IN THIS FILE

//DO NOT CHANGE THE NAMES OF ANY EXISTING FUNCTIONS

public class Dijkstra {

public static int [][] Dijkstra_alg( int n, int e, int mat[][], int s) {

//Write your code here to calculate shortest paths and usp values from source to all vertices

//This method will have four inputs (Please see testcase file)

//This method should return a two dimensional array as output (Please see testcase file)

}

}

Suppose you have a weighted, undirected graph G with positive edge weights and a start vertex s a) Describe a modification of Dijkstra's algorithm (Chapter 24 of Introduction-to-algorithm-3rd Edition Solution) that runs (asymptotically) as fast as the original algorithm, and assigns a binary value usp[u] to every vertex u in G, so that usp[u if and only if there is a unique shortest path from s to u. By definition usp[s. In addition to your modification, be sure to provide arguments for both the correctness and time bound of your algorithm, and an example. Algorithm: Relax (u,v,w) if (d[v]> d[u] + w(u.v)) d[v] = d[u] + w(u,v) usply] = usplu] else if d[y] = d[u] + w(u,v) usp[v] false Dijkstra (G,w,s) Initialize-single-source (G,s) For all vertex v usp[y] = true while Q != { } u = Extract-Min (Q) for each vertex v in Adj[u] relax (u,v.w) Suppose you have a weighted, undirected graph G with positive edge weights and a start vertex s a) Describe a modification of Dijkstra's algorithm (Chapter 24 of Introduction-to-algorithm-3rd Edition Solution) that runs (asymptotically) as fast as the original algorithm, and assigns a binary value usp[u] to every vertex u in G, so that usp[u if and only if there is a unique shortest path from s to u. By definition usp[s. In addition to your modification, be sure to provide arguments for both the correctness and time bound of your algorithm, and an example. Algorithm: Relax (u,v,w) if (d[v]> d[u] + w(u.v)) d[v] = d[u] + w(u,v) usply] = usplu] else if d[y] = d[u] + w(u,v) usp[v] false Dijkstra (G,w,s) Initialize-single-source (G,s) For all vertex v usp[y] = true while Q != { } u = Extract-Min (Q) for each vertex v in Adj[u] relax (u,v.w)