In Java please write a program that does the following Using Dijkstra\'s algorit

Question

In Java please write a program that does the following

Using Dijkstra's algorithm, write a Java program to find the lengths of the shortest paths from a vertex i to all the other vertices in a undirected, connected, weighted simple graph G whose vertices are labeled from thru v? . The inputs to your program will be the number of vertices followed by the weighted adjacency matrix of a graph as well as the initial vertex number from which the shortest path lengths are to be computed. The output will be the shortest path lengths from the vertex to all the other vertices in a nice format. Input VO V2 V4 Vo 2 3 00 vi 2 0 0 570 V2 3 0 0 5 0 Va 5 0 2 V4 0 75 1 3 Vs 0 0 3 0

Explanation / Answer

Code

// A Java program for Dijkstra's single source shortest path algorithm.

// The program is for adjacency matrix representation of the graph

import java.util.*;

import java.lang.*;

import java.io.*;

class Dijkstra

{

int getMinDistance(int distance[], Boolean isSet[], int numberOfVertices)

{

// Initialize value with maximum integer

int min = Integer.MAX_VALUE;

// take position as -1

int position=-1;

for (int v = 0; v < numberOfVertices; v++)

if (isSet[v] == false && distance[v] <= min)

{

min = distance[v];

position = v;

}

return position;

}

void shortestPath(int adjacencyMatrix[][], int source, int numberOfVertices)

{

// the output array which holds the distance of all the vertices from source

int distance[] = new int[numberOfVertices];

// isSet[i] will true if vertex i is included in shortest

// path tree or shortest distance from source to i is finalized

Boolean isSet[] = new Boolean[numberOfVertices];

// Set all distances as max integer value and isSet[] as false

for (int i = 0; i < numberOfVertices; i++)

{

distance[i] = Integer.MAX_VALUE;

isSet[i] = false;

}

// Distance of source vertex from itself is always 0

distance[source] = 0;

// Find shortest path for all vertices

for (int count = 0; count < numberOfVertices-1; count++)

{

int u = getMinDistance(distance, isSet, numberOfVertices);

// Mark the picked vertex as processed

isSet[u] = true;

// Update distancevalue of the adjacent vertices of the

// picked vertex.

for (int v = 0; v < numberOfVertices; v++)

// Update distance[v] only if

// 1. It is not in isSet

// 2. there is an edge from u to v

// 3. total weight of path from source to v through u is smaller than current

// value of distance[v]

if (!isSet[v] && adjacencyMatrix[u][v]!=0 &&

distance[u] != Integer.MAX_VALUE &&

distance[u]+adjacencyMatrix[u][v] < distance[v])

distance[v] = distance[u] + adjacencyMatrix[u][v];

}

// print the result

System.out.println(" Source - > destination = Distance");

for (int i = 0; i < numberOfVertices; i++)

System.out.println(source + " -> " + i+ " : "+distance[i]);

}

// Main

public static void main (String[] args)

{

int adjacenyMatrix[][] = new int[][]{{0, 2, 3, 0, 0, 0},

{2, 0, 0, 5, 7, 0},

{3, 0, 0, 0, 5, 0},

{0, 5, 0, 0, 1, 2},

{0, 7, 5, 1, 0, 3},

{0, 0, 0, 2, 3, 0}

};

Dijkstra dijkstra = new Dijkstra();

Scanner scanner = new Scanner(System.in);

System.out.print(" Enter number of vertices : ");

int numberOfVertices = scanner.nextInt();

  

System.out.print(" Enter source node: ");

int source = scanner.nextInt();

  

dijkstra.shortestPath (adjacenyMatrix, source, numberOfVertices );

}

}

Output

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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