Implement the following pseudocode for Bellman-Ford Algorithm using Java functio

Question

Implement the following pseudocode for Bellman-Ford Algorithm using Java

function <predecessors> Bellman-Ford(G, source)
    for i in 1 to |U| do
        distance[i] = +inf
        predecessors[i] = null

    distance[source] = 0

    for i in 1 to (|U| - 1) do
        for each Edge e in Edges(G) do
            if distance[e.from] + length(e) < distance[e.to] do
                distance[e.to] = distance[e.from] + length(e)
                predecessors[e.to] = e.from
              
    for each Edge e in Edges(G) do
        if distance[e.from] + length(e) < distance[e.to] do
            error("Graph contains cycles of negative length")
  
    return predecessors     

Explanation / Answer

Code:

import java.util.Scanner;

public class Main
{
private int distances[];
private int numOfVertices;
public static final int MAX_VALUE = 999;

public Main(int numOfVertices)
{
this.numOfVertices = numOfVertices;
distances = new int[numOfVertices + 1];
}

public void MainEvaluation(int source, int adjMatrix[][])
{
for (int node = 1; node <= numOfVertices; node++)
{
distances[node] = MAX_VALUE;
}

distances[source] = 0;
for (int node = 1; node <= numOfVertices - 1; node++)
{
for (int sourceNode = 1; sourceNode <= numOfVertices; sourceNode++)
{
for (int distinationNode = 1; distinationNode <= numOfVertices; distinationNode++)
{
if (adjMatrix[sourceNode][distinationNode] != MAX_VALUE)
{
if (distances[distinationNode] > distances[sourceNode]
+ adjMatrix[sourceNode][distinationNode])
distances[distinationNode] = distances[sourceNode]
+ adjMatrix[sourceNode][distinationNode];
}
}
}
}

for (int sourceNode = 1; sourceNode <= numOfVertices; sourceNode++)
{
for (int distinationNode = 1; distinationNode <= numOfVertices; distinationNode++)
{
if (adjMatrix[sourceNode][distinationNode] != MAX_VALUE)
{
if (distances[distinationNode] > distances[sourceNode]
+ adjMatrix[sourceNode][distinationNode])
System.out.println("The Graph contains negative egde cycle");
}
}
}

for (int vertex = 1; vertex <= numOfVertices; vertex++)
{
System.out.println("distance of source " + source + " to "
+ vertex + " is " + distances[vertex]);
}
}

public static void main(String... arg)
{
int numOfVertices = 0;
int source;
Scanner scanner = new Scanner(System.in);

System.out.print("Enter the number of vertices");
numOfVertices = scanner.nextInt();

int adjMatrix[][] = new int[numOfVertices + 1][numOfVertices + 1];
System.out.println("Enter the adjacency matrix");
for (int sourceNode = 1; sourceNode <= numOfVertices; sourceNode++)
{
for (int distinationNode = 1; distinationNode <= numOfVertices; distinationNode++)
{
adjMatrix[sourceNode][distinationNode] = scanner.nextInt();
    if (sourceNode == distinationNode)
{
adjMatrix[sourceNode][distinationNode] = 0;
continue;
}
if (adjMatrix[sourceNode][distinationNode] == 0)
{
adjMatrix[sourceNode][distinationNode] = MAX_VALUE;
}
}
}

System.out.println("Enter the source vertex");
source = scanner.nextInt();

Main Main = new Main(numOfVertices);
Main.MainEvaluation(source, adjMatrix);
scanner.close();  
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects