Modify the following code for Dijkstra\'s Algorithm to solve Bellman-Ford Algori

Question

Modify the following code for Dijkstra's Algorithm to solve Bellman-Ford Algorithm.

import java.io.*;
import java.lang.*;
import java.util.*;

public class Dijkstra
{

    private int V ;
    int graph[][];
    int src;
  
    public Dijkstra(int V,int[][] graph,int src)
    {
        this.V=V;
        this.graph=graph;
        this.src=src;
    }
  
    public static Dijkstra getDijkstraInstance()
    {
        int V;
        int[][] graph;
        int src;
        Scanner in=new Scanner(System.in);
        System.out.println("Enter number of vertices:");
        V=in.nextInt();
        in.nextLine();
        graph=new int[V][];
        System.out.println("Enter the matrix, one row a time, each number separated with ","(no spaces):");
        for(int i=0;i<V;i++)
        {
            String line=in.nextLine();
            String[] lineArr=line.split(",");
            int[] iArr=new int[lineArr.length];
            for(int j=0;j<iArr.length;j++)
            {
                iArr[j]=Integer.parseInt(lineArr[j]);
            }
            graph[i]=iArr;
        }
      
        System.out.println("Enter source vertex:");
        src=in.nextInt();
        in.nextLine();
        return new Dijkstra(V,graph,src);
    }

    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index = -1;

        for (int v = 0; v < V; v++)
        {
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }
        }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " " + dist[i]);
        }
    }

    void algorithm()
    {
        int dist[] = new int[V];
        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
        dist[src] = 0;
        for (int count = 0; count < V - 1; count++)
        {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;
            for (int v = 0; v < V; v++)
            {
                if (!sptSet[v] && graph[u][v] != 0
                        && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist, V);
    }
  
    public void setGraph(int[][] graph)
    {
        this.graph=graph;
        V=graph.length;
    }
  
    public void setSource(int s)
    {
        src=s;
    }
  
    public static void main(String[] args)
    {
        Dijkstra t = Dijkstra.getDijkstraInstance();
        t.algorithm();
    }
}

Explanation / Answer

The primary difference in the function of the two algorithms is that Dijkstra's algorithm cannot handle negative edge weights. Bellman-Ford's algorithm can handle some edges with negative weight. However, if there is a negative cycle there is no shortest path.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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