Use and implement the following pseudocode for Dijkstra\'s Algorithm and convert

Question

 Use and implement the following pseudocode for Dijkstra's Algorithm and convert it into working Java code. Make sure you follow the structure of the pseudocode.       function Dijkstra(Graph, source):          create vertex set Q          for each vertex v in Graph:             // Initialization            dist[v]  INFINITY                  // Unknown distance from source to v            prev[v]  UNDEFINED                 // Previous node in optimal path from source            add v to Q                          // All nodes initially in Q (unvisited nodes)         dist[source]  0                        // Distance from source to source              while Q is not empty:           u  vertex in Q with min dist[u]    // Source node will be selected first           remove u from Q                       for each neighbor v of u:           // where v is still in Q.               alt  dist[u] + length(u, v)               if alt < dist[v]:               // A shorter path to v has been found                   dist[v]  alt                    prev[v]  u         return dist[], prev[] 

Explanation / Answer

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
static final int V=6;
int minDistance(int dist[], Boolean sptSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;

for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}

return min_index;
}
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" "+dist[i]);
}

void dijkstra(int graph[][], int src)
{
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];

for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

printSolution(dist, V);
}
public static void main (String[] args)
{
/* Let us create the example graph discussed above */
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.