Hello.

I am trying to implement Dijkstra's algorithm.

I am trying to follow the following pseudo code :

I got stuck on few steps and I need your help.

I did the following:

/* ShortestPaths.java This template includes some testing code to help verify the implementation. To interactively provide test inputs, run the program with java ShortestPaths To conveniently test the algorithm with a large input, create a text file containing one or more test graphs (in the format described below) and run the program with java ShortestPaths file.txt where file.txt is replaced by the name of the text file. The input consists of a series of graphs in the following format: ... Entry A[i][j] of the adjacency matrix gives the weight of the edge from vertex i to vertex j (if A[i][j] is 0, then the edge does not exist). Note that since the graph is undirected, it is assumed that A[i][j] is always equal to A[j][i]. An input file can contain an unlimited number of graphs; each will be processed separately. NOTE: For the purpose of marking, we consider the runtime (time complexity) of your implementation to be based only on the work done starting from the ShortestPaths() method. That is, do not not be concerned with the fact that the current main method reads in a file that encodes graphs via an adjacency matrix (which takes time O(n^2) for a graph of n vertices) */

import java.util.Scanner; import java.io.File; import java.io.FileNotFoundException; import java.util.PriorityQueue; import java.util.Stack; import java.util.LinkedList; import java.util.Iterator; import edu.princeton.cs.algs4.*; import java.util.*;

//Do not change the name of the ShortestPaths class public class ShortestPaths{

//TODO: Your code here public static int n;

static void ShortestPaths(int[][][] adj, int source){ n = adj.length; int [] d = new int[n];//current node int [] pi = new int[n];//previous node int S;//u+e.weight EdgeWeightedGraph G = new EdgeWeightedGraph(n); for (int i = 0; i pq = new IndexMinPQ(n); pq.insert(source, d[source]); while(!pq.isEmpty()) { int u = pq.delMin(); S = S+u;<>

// I'M STUCK HERE! I DON'T KNOW HOW TO CONTINUE OR IF WHAT I DID IS CORRECT. PLEASE HELP! for(Edge e : G.adj(u)) { int v = e.either(); int w = e.other(v); if (d[u] + e.weight() 0){ //If a file argument was provided on the command line, read from the file try{ s = new Scanner(new File(args[0])); } catch(java.io.FileNotFoundException e){ System.out.printf("Unable to open %s ",args[0]); return; } System.out.printf("Reading input values from %s. ",args[0]); } else{ //Otherwise, read from standard input s = new Scanner(System.in); System.out.printf("Reading input values from stdin. "); } int graphNum = 0; double totalTimeSeconds = 0; //Read graphs until EOF is encountered (or an error occurs) while(true){ graphNum++; if(graphNum != 1 && !s.hasNextInt()) break; System.out.printf("Reading graph %d ",graphNum); int n = s.nextInt(); int[][][] adj = new int[n][][]; int valuesRead = 0; for (int i = 0; i edgeList = new LinkedList(); for (int j = 0; j 0) { edgeList.add(new int[]{j, weight}); } valuesRead++; } adj[i] = new int[edgeList.size()][2]; Iterator it = edgeList.iterator(); for(int k = 0; k 0)?totalTimeSeconds/graphNum:0); } }

Dijkstra(VE,s) For v in V Q BuildPriorityQueue(V, d While Q not empty u - ExtractMin(Q) S SUu For v in Adj[u] If d[u]+ w(u,v) d[v] UpdatePQ(v, div]) Dijkstra(VE,s) For v in V Q BuildPriorityQueue(V, d While Q not empty u - ExtractMin(Q) S SUu For v in Adj[u] If d[u]+ w(u,v) d[v] UpdatePQ(v, div])