Write a Jave program we put together a set of matrices that would be generated b

Question

Write a Jave program

we put together a set of matrices that would be generated by the Floyd-Warshall algorithm. These matrices give us the value of an optimal solution, but we still want to construct the optimal solution itself: given a pair of vertices vi , vj what would the shortest path through the graph actually be?

APSP Solution. Given a predecessor matrix, print the shortest path for a given source s and destination d. This algorithm should operate on the last predecessor matrix (n)

Pseudocode for this problem is given below.

Print-SP(, i, j)

if i = j

print i

else if ij= NIL

print “No path from i to j, bummer!”

else

Print-SP(, i, ij)

print j

Sample Input (Right-Hand Columns for Copy-Paste into Source Code)

D(5) =   

1

2

3

4

5

1

0

1

-3

2

-4

2

3

0

-4

1

-1

3

7

4

0

5

3

4

2

-1

-5

0

-2

5

8

5

1

6

0

{ {0, 1, -3, 2, -4},

  {3, 0, -4, 1, -1},

  {7, 4, 0, 5, 3},

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

  {8, 5, 1, 6, 0} }

D(5) =   

1

2

3

4

5

1

0

1

-3

2

-4

2

3

0

-4

1

-1

3

7

4

0

5

3

4

2

-1

-5

0

-2

5

8

5

1

6

0

{ {0, 1, -3, 2, -4},

  {3, 0, -4, 1, -1},

  {7, 4, 0, 5, 3},

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

  {8, 5, 1, 6, 0} }

Explanation / Answer

package com.sanfoundry.graph;

import java.util.Scanner;

public class FloydWarshallShortestPath
{
private int distancematrix[][];
private int numberofvertices;
public static final int INFINITY = 999;

public FloydWarshallShortestPath(int numberofvertices)
{
distancematrix = new int[numberofvertices + 1][numberofvertices + 1];
this.numberofvertices = numberofvertices;
}

public void floydwarshall(int adjacencymatrix[][])
{
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
distancematrix[source][destination] = adjacencymatrix[source][destination];
}
}
for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)
{
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
if (distancematrix[source][intermediate]
+ distancematrix[intermediate][destination] < distancematrix[source][destination])
distancematrix[source][destination] = distancematrix[source][intermediate]
+ distancematrix[intermediate][destination];
}
}
}
for (int source = 1; source <= numberofvertices; source++)
System.out.print(" " + source);
System.out.println();
for (int source = 1; source <= numberofvertices; source++)
{
System.out.print(source + " ");
for (int destination = 1; destination <= numberofvertices; destination++)
{
System.out.print(distancematrix[source][destination] + " ");
}
System.out.println();
}
}

public static void main(String... arg)
{
int adjacency_matrix[][];
int numberofvertices;
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of vertices");
numberofvertices = scan.nextInt();
adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int source = 1; source <= numberofvertices; source++)
{
for (int destination = 1; destination <= numberofvertices; destination++)
{
adjacency_matrix[source][destination] = scan.nextInt();
if (source == destination)
{
adjacency_matrix[source][destination] = 0;
continue;
}
if (adjacency_matrix[source][destination] == 0)
{
adjacency_matrix[source][destination] = INFINITY;
}
}
}
System.out.println("The Transitive Closure of the Graph");
FloydWarshallShortestPath floydwarshall = new FloydWarshallShortestPath(
numberofvertices);
floydwarshall.floydwarshall(adjacency_matrix);
scan.close();
}
}

import java.util.Scanner;

/** Class Warshall **/
public class Warshall
{
private int V;
private boolean[][] tc;
/** Function to make the transitive closure **/
public void getTC(int[][] graph)
{
this.V = graph.length;
tc = new boolean[V][V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
if (graph[i][j] != 0)
tc[i][j] = true;
tc[i][i] = true;
}
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (tc[j][i])
for (int k = 0; k < V; k++)
if (tc[j][i] && tc[i][k])
tc[j][k] = true;   
}
}
}
/** Funtion to display the trasitive closure **/
public void displayTC()
{
System.out.println(" Transitive closure : ");
System.out.print(" ");
for (int v = 0; v < V; v++)
System.out.print(" " + v );
System.out.println();
for (int v = 0; v < V; v++)
{
System.out.print(v +" ");
for (int w = 0; w < V; w++)
{
if (tc[v][w])
System.out.print(" * ");
else
System.out.print(" ");
}
System.out.println();
}
}

/** Main function **/
public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Warshall Algorithm Test ");
/** Make an object of Warshall class **/
Warshall w = new Warshall();


System.out.println("Enter number of vertices ");
int V = scan.nextInt();

/** get graph **/
System.out.println(" Enter matrix ");
int[][] graph = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
graph[i][j] = scan.nextInt();

w.getTC(graph);
w.displayTC();
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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