Implement Dijkstra\'s algorithm (140 points if Q is implemented by a min-heap: 1

Question

Implement Dijkstra's algorithm (140 points if Q is implemented by a min-heap: 130 points if Q is implemented by an array) Number the vertices from 1 to n (Suppose G has n vertices) and the source node to be 1. Adjacent lists G: (i) define an array Adj of n nodes, where Adj[i] leads a linked list that saves the neighbors of vertex i. (ii) Each node in linked list Adj[i] contains (a) a neighbor (say j) of i, (b) the weight of edge (ij), and (c) the link to the next node. Array p, where p[i] is the current parent of i, and array d, where d[i] is the current distance from 1 to i. A beginning, d[l] = 0 and d[i] = infinite for i > 1, and p[i] = NIL for all i. Priority queue Q: there are n items (one item for each vertex of G) in Q at the beginning, where an item contains (i) a vertex name, say i, and (ii) d[i] (current distance from 1 to i), where d[i] is used as key for Q. At beginning, d[l] = 0 and d[i] = infinite fori > 1. Structure of the implementation method: dijkstra(G: w, s) which return p main method: main() { input the graph in Example 3: create adjacent lists of G, assign value to w, assign value to s; call Dijkstra(G,w,s); print path of s to each vertex using p;} Requirements A priority queue Q is used for the unprocessed vertices Analyze the time complexity of your implementation using O-notation. Note that the time complexity also depends on the data structures you used in the implementation. Use C# for implementation Submission Project description, Algorithm, Algorithm analysis, Description of your implementation including the data structures you use. The workload and contribution of each team member. Experiment output. Code.

Explanation / Answer

import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class DijkstraQueue
{
private int distances[];
private Queue<Integer> queue;
private Set<Integer> settled;
private int number_of_nodes;
private int adjacencyMatrix[][];

public DijkstraQueue(int number_of_nodes)
{
this.number_of_nodes = number_of_nodes;
distances = new int[number_of_nodes + 1];
settled = new HashSet<Integer>();
queue = new LinkedList<Integer>();
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
}

public void dijkstra_algorithm(int adjacency_matrix[][], int key)
{
int evaluationNode;
for (int p = 1; p <= number_of_nodes; p++)
for (int q = 1; q <= number_of_nodes; q++)
adjacencyMatrix[p][q] = adjacency_matrix[p][q];

for (int p = 1; p <= number_of_nodes; p++)
{
distances[p] = Integer.MAX_VALUE;
}

queue.add(key);
distances[key] = 0;

while (!queue.isEmpty())
{
evaluationNode = getNodeWithMinimumDistanceFromQueue();
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}

private int getNodeWithMinimumDistanceFromQueue()
{
int min ;
int node = 0;
Iterator<Integer> iterator = queue.iterator();
node = iterator.next();
min = distances[node];

for (int p = 1; p <= distances.length; p++)
{
if (queue.contains(p))
{
if (distances[p] <= min)
{
min = distances[p];
node = p;          
}
}
}
queue.remove(node);
return node;
}

private void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;

for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if (!settled.contains(destinationNode))
{
if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;
}
queue.add(destinationNode);
}
}
}
}

public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int key = 0;
Scanner scan = new Scanner(System.in);

try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

System.out.println("enter greph with weights");
for (int p = 1; p <= number_of_vertices; p++)
{
for (int q = 1; q <= number_of_vertices; q++)
{
adjacency_matrix[p][q] = scan.nextInt();
if (p == q)
{
adjacency_matrix[p][q] = 0;
continue;
}
if (adjacency_matrix[p][q] == 0)
{
adjacency_matrix[p][q] = Integer.MAX_VALUE;
}
}
}

System.out.println("Enter the key ");
source = scan.nextInt();
DijkstraQueue dijkstrasQueue = new DijkstraQueue(number_of_vertices);
dijkstrasQueue.dijkstra_algorithm(adjacency_matrix, source);

System.out.println("The Shorted Path to all nodes are ");
for (int p = 1; p <= dijkstrasQueue.distances.length - 1; p++)
{
System.out.println(source + " to " + p + " is " + dijkstrasQueue.distances[p]);
}
} catch (InputMismatchException inputMismatch)
{
System.out.println("invalid input formate");
}
scan.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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