0

i am doing a group project concerning graph my part is finding the minimal cost the teacher tried to help us out with the group work by putting up code for the parts for use to follow.

i have errors when i compiled the code that the teacher give.

the error is with followPath it said that the method followPath int is not declared with type Graph.

no matter what i did to fix it it did not work so i need help

plus she said it needed modification but it due in another day and since i am still learning java and have not done graph before or dijkstra i need help with the error and the modification.we are suppose to read the cities from afile so please help.

```
import java.io.*;
import java.util.*;
public class Graph {
GVertex[] vertex;
int numV;
PrintWriter out;
public Graph(PrintWriter fout, int n) {
numV = n;
vertex = new GVertex[n+1];
vertex[0] = new GVertex("#");
out = fout;
}
public void buildGraph(Scanner in) {
for (int j = 1; j <= numV; j++) vertex[j] = new GVertex(in.next());
for (int j = 1; j <= numV; j++) {
String vertexID = in.next();
int numEdges = in.nextInt();
for (int k = 1; k <= numEdges; k++) {
String adjID = in.next();
int weight = in.nextInt();
addEdge(vertexID, adjID, weight);
}
}
} //end buildGraph
private void addEdge(String X, String Y, int weight) {
//add an edge X -> Y with a given weight
int j, k;
//find X in the list of nodes; its location is j
for (j = 1; j <= numV; j++) if (X.equals(vertex[j].id)) break;
//find Y in the list of nodes; its location is k
for (k = 1; k <= numV; k++) if (Y.equals(vertex[k].id)) break;
if (j > numV || k > numV) {
System.out.printf("No such edge: %s to %s\n", X, Y);
System.exit(1);
}
GEdge ge = new GEdge(k, weight); //create edge vertex
// add it to the list of edges, possible empty, from X;
// it is added so that the list is in order by vertex id
GEdge prev, curr;
prev = curr = vertex[j].firstEdge;
while (curr != null && Y.compareTo(vertex[curr.child].id) > 0) {
prev = curr;
curr = curr.nextEdge;
}
if (prev == curr) {
ge.nextEdge = vertex[j].firstEdge;
vertex[j].firstEdge = ge;
}
else {
ge.nextEdge = curr;
prev.nextEdge = ge;
}
} //end addEdge()
void printGraph() {
for (int j = 1; j <= numV; j++) {
out.printf("%s: ", vertex[j].id);
GEdge p = vertex[j].firstEdge;
while (p != null) {
out.printf("%s %d ", vertex[p.child].id, p.weight);
p = p.nextEdge;
}
out.printf("\n");
}
out.printf("\n");
} //end printGraph
public void Dijkstra(int s) {
final int Infinity = 9999;
int[] heap = new int[numV+1];
int[] heapLoc = new int[numV+1];
//heapLoc[j] gives the position in heap of vertex j
//if heapLoc[j] = k, then heap[k] contains j
for (int j = 1; j <= numV; j++) {
vertex[j].cost = Infinity;
vertex[j].parent = 0;
}
vertex[s].cost = 0;
for (int j = 1; j <= numV; j++) heap[j] = heapLoc[j] = j;
heap[1] = s; heap[s] = 1; heapLoc[s] = 1; heapLoc[1] = s;
int heapSize = numV;
while (heapSize > 0) {
int u = heap[1];
if (vertex[u].cost == Infinity) break; //no paths to the other vertices siftDown(heap[heapSize], heap, 1, heapSize-1, heapLoc);
GEdge p = vertex[u].firstEdge;
while (p != null) {
if (vertex[u].cost + p.weight < vertex[p.child].cost) {
vertex[p.child].cost = vertex[u].cost + p.weight;
vertex[p.child].parent = u;
siftUp(heap, heapLoc[p.child], heapLoc);
}
p = p.nextEdge;
}
--heapSize;
} //end while
for (int j = 1; j <= numV; j++) {
out.printf("Cost to %s: %d, Path: ", vertex[j].id, vertex[j].cost);
followPath(j);
out.printf("\n");
}
} //end Dijkstra
private void siftUp(int heap[], int n, int[] heapLoc) {
//sifts up heap[n] so that heap[1..n] contains a heap based on cost
int siftItem = heap[n];
int child = n;
int parent = child / 2;
while (parent > 0) {
if (vertex[siftItem].cost >= vertex[heap[parent]].cost) break;
heap[child] = heap[parent]; //move down parent
heapLoc[heap[parent]] = child;
child = parent;
parent = child / 2;
}
heap[child] = siftItem;
heapLoc[siftItem] = child;
} //end siftUp
}
```