How can modify this program to implement two of the shortest- path algorithms: D
ID: 3735529 • Letter: H
Question
How can modify this program to implement two of the shortest- path algorithms: Dijkstra's and Bellman-Ford
Graph.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.io.*;
public class Graph
{
private static final double INF = Double.MAX_VALUE;
private ArrayList table = new ArrayList();
int numV = 0;
private Map vertexMap = new HashMap();
public Graph()
{
table = new ArrayList();
numV = 0;
vertexMap = new HashMap();
}
public void addEdge(String srcName, String destName, double cost)
{
Vertex v = getVertex(srcName);
Vertex w = getVertex(destName);
v.adj.add(new Edge(w, cost));
}
public void addUndirectedEdge(String srcName, String destName, double cost)
{
Vertex v = getVertex(srcName);
Vertex w = getVertex(destName);
v.adj.add(new Edge(w, cost));
w.adj.add(new Edge(v, cost));
}
private Vertex getVertex(String name)
{
Vertex v;
Integer i = vertexMap.get(name);
if (i == null) { // first time we've seen this vertex name
v = new Vertex(name);
table.add(v);
vertexMap.put(name, numV);
numV++;
}
else
v = table.get(i);
return v;
}
public void printGraph()
{
for(Vertex v : table) {
System.out.print(v.name + ":");
for(Edge e : v.adj) {
System.out.print(" " + e.dest.name + "(" + e.cost + ")");
}
System.out.println();
}
}
public void dijkstra(String sourceName)
{
}
public void bellmanFord(String sourceName)
{
}
public double getDist(String vname)
{
return 0.0;
}
public ArrayList getPath(String vname)
{
return new ArrayList();
}
public void readGraph(String fname)
//
// read in a graph, where file fname has following format:
//
// first line: single integer n = number of edges
// each of next n lines: two Strings v1 v2 and double c indicating
// an edge from v1 to v2 with cost c
//
{
Scanner fin = null;
try {
fin = new Scanner(new FileInputStream(fname));
} catch (IOException e) {
System.out.println(e);
System.exit(-1);
}
int nedges = fin.nextInt();
for(int i=1; i<=nedges; i++) {
String v1 = fin.next();
String v2 = fin.next();;
double cost = fin.nextDouble();
addEdge(v1, v2, cost);
}
}
public static void main(String [] args)
//
// example driver program
//
{
Graph g = new Graph();
g.readGraph("bfexample.graph");
g.printGraph();
g.bellmanFord("v0");
ArrayList path = g.getPath("v3");
System.out.print("Path to v3:");
for(Vertex v : path) {
System.out.print(" " + v.name);
}
System.out.println(" Dist to v3: " + g.getDist("v3"));
}
}
Vertex.java
import java.util.*;
class Vertex
{
public String name;
public List adj;
public Vertex(String n)
{
name = n;
adj = new LinkedList();
}
}
Edge.java
public class Edge
{
public Vertex dest;
public double cost;
public Edge(Vertex w, double c)
{
dest = w;
cost = c;
}
}
a sample input file example.graph:
12
v0 v1 4
v0 v3 0
v0 v5 3
v0 v2 0
v2 v1 1
v3 v5 5
v4 v2 -3
v4 v3 -1
v5 v1 -1
v5 v3 -2
v5 v4 -3
v1 v3 1
Explanation / Answer
//Java Program to implement Djikstra's algorithm to find shortest path
import java.util.Scanner; //Scanner Function to take in the Input Values
public class Dijkstra
{
static Scanner scan; // scan is a Scanner Object
public static void main(String[] args)
{
int[] preD = new int[5];
int min = 999, nextNode = 0; // min holds the minimum value, nextNode holds the value for the next node.
scan = new Scanner(System.in);
int[] distance = new int[5]; // the distance matrix
int[][] matrix = new int[5][5]; // the actual matrix
int[] visited = new int[5]; // the visited array
System.out.println("Enter the cost matrix");
for (int i = 0; i < distance.length; i++)
{
visited[i] = 0; //initialize visited array to zeros
preD[i] = 0;
for (int j = 0; j < distance.length; j++)
{
matrix[i][j] = scan.nextInt(); //fill the matrix
if (matrix[i][j]==0)
matrix[i][j] = 999; // make the zeros as 999
}
}
distance = matrix[0]; //initialize the distance array
visited[0] = 1; //set the source node as visited
distance[0] = 0; //set the distance from source to source to zero which is the starting point
for (int counter = 0; counter < 5; counter++)
{
min = 999;
for (int i = 0; i < 5; i++)
{
if (min > distance[i] && visited[i]!=1)
{
min = distance[i];
nextNode = i;
}
}
visited[nextNode] = 1;
for (int i = 0; i < 5; i++)
{
if (visited[i]!=1)
{
if (min+matrix[nextNode][i] < distance[i])
{
distance[i] = min+matrix[nextNode][i];
preD[i] = nextNode;
}
}
}
}
for(int i = 0; i < 5; i++)
System.out.print("|" + distance[i]);
System.out.println("|");
int j;
for (int i = 0; i < 5; i++)
{
if (i!=0)
{
System.out.print("Path = " + i);
j = i;
do
{
j = preD[j];
System.out.print(" <- " + j);
}
while(j != 0);
}
System.out.println();
}
}
}
OUTPUT
12
v0 v1 4
v0 v3 0
v0 v5 3
v0 v2 0
v2 v1 1
v3 v5 5
v4 v2 -3
v4 v3 -1
v5 v1 -1
v5 v3 -2
v5 v4 -3
v1 v3 1
//Java Program to implement Bellman-Forn Algorithm for finding shortest path
import java.util.*;
import java.lang.*;
import java.io.*;
// A class to represent a connected, directed and weighted graph
class Graph
{
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph,int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i=0; i<V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can
// have at-most |V| - 1 edges
for (int i=1; i<V; ++i)
{
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u]!=Integer.MAX_VALUE &&
dist[u]+weight<dist[v])
dist[v]=dist[u]+weight;
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE &&
dist[u]+weight < dist[v])
System.out.println("Graph contains negative weight cycle");
}
printArr(dist, V);
}
// A utility function used to print the solution
void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i=0; i<V; ++i)
System.out.println(i+" "+dist[i]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.