Can some one help me to modify the project in java to implement two of the shortest- path algorithms: Dijkstra's and Bellman-Ford. Specifically you must do the following: 1. Add code to the empty methods dijkstra(String sourceName) and bellmanFord(String sourceName) to implement the corresponding shortest-path algorithms.// I did dijkstra(String sourceName) but i don't know if right 2. Modify the code for the getDist(String vname) and getPath(String vname) methods. These methods are to be used after a call to either dijkstra() or bellmanFord() to obtain the minimum cost distance and path from the source vertex to vertex vname. The latter of these methods should return an answer of type ArrayList.

Note: an efficient implementation of Dijkstra's algorithm will involve the use of a priority queue. Java provides a PriorityQueue class which you can use, but you must also create a class that implements the Comparator interface.

The three Java files {Graph.java, Vertex.java and Edge.java }

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();

}

}

/*private void clearAll() {

for (Integer i : vertexMap.values()) {

Vertex v = new Vertex(""+i);

v.reset();

}

}*/

public void dijkstra(String sourceName)

{

PriorityQueue pq = new PriorityQueue( );

//Vertex start = new Vertex(sourceName);

Vertex start = getVertex(sourceName);

Integer i = vertexMap.get(sourceName);

if( i == null )

throw new NoSuchElementException( "Start vertex not found" );

// clearAll();

pq.add( new Path( start , 0 ) );

start.dist = 0;

int nodesSeen = 0;

while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )

{

Path vrec = pq.remove( );

Vertex v = vrec.dest;

if( v.scratch != 0 )

continue;

v.scratch = 1;

nodesSeen++;

for( Edge e : v.adj )

{

Vertex w = e.dest;

double cvw = e.cost;

if( cvw < 0 )

throw new GraphException( "Graph has negative edges" );

if( w.dist > v.dist + cvw )

{

w.dist = v.dist +cvw;

w.prev = v;

pq.add( new Path( w, w.dist ) );

}

}

}

}

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 double dist;

public Vertex prev;

public int scratch;

public Vertex(String n)

{

name = n;

adj = new LinkedList();

reset();

}

public void reset() {

dist = Graph.INF;

prev = null;

scratch = 0;

}

Edge.java

public class Edge

{

public Vertex dest;

public double cost;

public Edge(Vertex w, double c)

{

dest = w;

cost = c;

}

}

Path Class:

public class Path implements Comparable { public Vertex dest; public double cost; public Path( Vertex d, double c ) { dest = d; cost = c; } public int compareTo( Path rhs ) { double otherCost = rhs.cost; return cost < otherCost ? -1 : cost > otherCost ? 1 : 0; } }

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