dijkstra

[chinee]

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




}

[zw_jvdijk83]

You don't have that function here, so the compiler doesn't know what to call.

[chinee]

that was all that the teacher give, is it that i have to create a function like public int followPath() but what goes inside the function and where exactly would the main go because in other dijkstra's i see the main at the end but those are different from this. thank you

[chinee]

ok i tried to add the function followPath() but i am not sure what is to go inside. and i created the main with the read file so the file could be read but i am getting errors
1. line 108 says illegal start of expression public static followPath() it is pointing to the p in public.
2.the second error is the same as the first but it is pointing to the s in static.
3.the third error say ; expected public static followPath() and is pointing at (.
4. the fourth error is in line 129 which says illegal start of expression public static void main (String[] args) and it is pointing at the p in public.
5.this error is the same as the fourth but it is pointing at the s in static.
6. the sixth error is just like above except it is poing at the space between static and void.
7.the seventh and the eight error is the same it is pointing at the a in args and the closing bracketin that sentence respectively.

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
    public static followPath()){
        int path =  path;
    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");
    }
    }

    /* public String[] readFile(String fileName) throws FileNotFoundException {
            Scanner input = new Scanner(new File("graphs.txt"));
            String line = "";
            while (input.hasNext()) {
                line = line.concat(input.nextLine());
            }
            String[] graph = line.split("");
            return graph;

        }*/


    public static void main(String[] args){

         in = new Scanner(new FileReader("graphs.txt"));
                String line = " ";
            Dijkstra dij = new Dijkstra();
                line = in.nextLine();
                     while (!line.equals("END"))
                        {
                            try{
                            StringTokenizer st = new StringTokenizer(line, "\n");
                            String vertex = st.nextToken();
                            v = new Vertex(vertex);
                            a.insert(vertex, v);
                            a.display();
                            }

                            catch (NoSuchElementException exception){
                            System.out.println("File not found");
                            }//end catch
                    //}//end catch

                 }//end while

        /*final String TEST = "/graphs.txt";
        Scanner input = new Scanner(new File(TEST));
        String line = "";
        while (input.hasNext()) {
            line = line.concat(input.nextLine());
        }
        String[] graph = line.split(" ");

        for (int i = 0; i < graph.length; i++) {
            System.out.println(graph[i]);
        }*/

    }
} //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;
    }//end while
    heap[child] = siftItem;
    heapLoc[siftItem] = child;
} //end siftUp




}