Find a Pseudocode for this program and the complexity: import java.util.Priority

Question

Find a Pseudocode for this program and the complexity:

import java.util.PriorityQueue;

import java.util.List;

import java.util.ArrayList;

import java.util.Collections;

class Vertex implements Comparable

{

public final String name;

public Edge[] adjacencies;

public double minDistance = Double.POSITIVE_INFINITY;

public Vertex previous;

public Vertex(String argName)

{

name = argName;

}

public String toString()

{

return name;

}

public int compareTo(Vertex other)

{

return Double.compare(minDistance, other.minDistance);

}

}

class Edge

{

public final Vertex target;

public final double weight;

public Edge(Vertex argTarget, double argWeight)

{

target = argTarget; weight = argWeight;

}

}

public class Dijkstra

{

public static void computePaths(Vertex source)

{

source.minDistance = 0.;

PriorityQueue vertexQueue = new PriorityQueue();

vertexQueue.add(source);

while (!vertexQueue.isEmpty())

{

Vertex u = vertexQueue.poll();

// Visit each edge exiting u for (Edge e : u.adjacencies)

{ Vertex v = e.target; double weight = e.weight;

double distanceThroughU = u.minDistance + weight;

if (distanceThroughU < v.minDistance)

{ vertexQueue.remove(v);

v.minDistance = distanceThroughU ;

v.previous = u; vertexQueue.add(v);

}

}

}

}

public static List getShortestPathTo(Vertex target)

{

List path = new ArrayList();

for (Vertex vertex = target;

vertex != null;

vertex = vertex.previous)

path.add(vertex);

Collections.reverse(path);

return path;

}

public static void main(String[] args)

{

// mark all the vertices Vertex

WA = new Vertex("WA");

Vertex CA1 = new Vertex("CA1");

Vertex CA2 = new Vertex("CA2");

Vertex UT = new Vertex("UT");

Vertex CO = new Vertex("CO");

Vertex TX = new Vertex("TX");

Vertex NE = new Vertex("NE");

Vertex IL = new Vertex("IL");

Vertex PA = new Vertex("PA");

Vertex GA = new Vertex("GA");

Vertex 11 = new Vertex("11");

Vertex NY= new Vertex(“NY”);

Vertex NJ= new Vertex(“NJ”);

Vertex DC=new Vertex(“DC”);

// set the edges and weight

WA.adjacencies = new Edge[]{ new Edge(CA1, 1050) };

CA1.adjacencies = new Edge[]{ new Edge(CA2, 600) };

CA2.adjacencies = new Edge[]{ new Edge(CA1, 600) };

UT.adjacencies = new Edge[]{ new Edge(CO, 600) };

CO.adjacencies = new Edge[]{ new Edge(NE, 600) };

TX.adjacencies = new Edge[]{ new Edge(DC, 1800) }

; NE.adjacencies = new Edge[]{ new Edge(CO, 600) };

IL.adjacencies = new Edge[]{ new Edge(NE, 750) };

PA.adjacencies = new Edge[]{ new Edge(NJ, 300) };

GA.adjacencies = new Edge[]{ new Edge(PA, 750) };

11.adjacencies = new Edge[]{ new Edge(NY, 600) };

NY.adjacencies = new Edge[]{ new Edge(DC, 300) };

NJ.adjacencies = new Edge[]{ new Edge(DC, 150) };

DC.adjacencies = new Edge[]{ new Edge(NJ, 150) };

computePaths(A);

// run Dijkstra System.out.println("Distance to " + Z + ": " + Z.minDistance);

List path = getShortestPathTo(Z); System.out.println("Path: " + path); } }

Explanation / Answer

Algorithm:

Step 1:Intiliase distance matrix of vertices with positive infinity

step 2:Create priority queue (pq).It stores (weight,vertex) pair.

step 3:Insert source vertex in queue and mark its distance as 0.

step 4:While pq empty do:

i)remove minimum vertex from pq and let it be u

ii)For adjnacent of u do:

If dist[v] > dist[u] + weight(u, v) do:

dist[v] = dist[u] + weight(u, v)

insert v into pq

Step 5:Print dist array for shortest path

================================================================

Time complexity:

O(ELogV)

as O(E) vertices and O(Logv) to sort them

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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