[jcs224]

The objective of this in lab is to continue Dijkstra's algorithm to print out the shortest paths from a given source vertex to ALL of the remaining vertices in a nice format, e.g.:

The shortest path from vertex 2 to vertex 0 is:
2 -> 1 -> 4 -> 0 (distance = 24.5)
The shortest path from vertex 2 to vertex 1 is:
2 -> 1 (distance = 6.5)
The shortest path from vertex 2 to vertex 3 is:
2 -> 6 -> 10 -> 3 (distance = 32.0)
etc.

Basically the input is a text file. Here is my example:

9
0 1 10.0
0 3 25.0
1 2 5.0
1 4 15.0
1 5 12.0
2 5 30.0
3 6 16.0
4 6 4.0
4 7 3.0
5 7 10.0
6 8 11.0
7 8 18.0

Now here is the main program that I have. I can get it to print out the final path, but i don't know how to print out the distance between each vertex in sequence like the assignment demands.

Right now my output looks like this:

The shortest path from vertex 0 to vertex 8 is:
1 -> 4 -> 6 -> 8 (Distance = 40.0)

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Joe
 */


import java.io.FileReader;
import java.io.IOException;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Scanner;

/** Program to solve a maze represented as a graph.
 *  This program performs a breadth-first search of the graph
 *  to find the "shortest" path from the start vertex to the
 *  end. It is assumed that the start vertex is 0, and the
 *  end vertex is numV-1.
 *  @author Koffman and Wolfgang
 */
public class TestDijkstra {

    /** Main method to solve the maze.
     *  pre: args[0] contains the name of the input file.
     *  @param args Command line argument
     */
    public static void main(String[] args) {
        int numV = 0; // The number of vertices.
        Graph theGraph = null;
        // Load the graph data from a file.
        try {
            Scanner scan = new Scanner(new FileReader("/Users/joesweeney/Desktop/testgraph4.txt"));
            theGraph = AbstractGraph.createGraph(scan, false, "Matrix");
            numV = theGraph.getNumV();
        } catch (IOException ex) {
            System.err.println("IO Error while reading graph");
            System.err.println(ex.toString());
            System.exit(1);
        }
        // Perform Dijkstra's algorithm:
        int start = 0; // starting  vertex
        int parent[] = new int[numV];
        double dist[] = new double[numV];
        DijkstrasAlgorithm.dijkstrasAlgorithm(theGraph, start, parent, dist);

        int destination = numV - 1;

        // Construct the path.
        Deque<Integer> thePath = new ArrayDeque<Integer>();
        int v = destination;
        while (parent[v] != -1) {
            thePath.push(new Integer(v));
            v = parent[v];
        }
        // Output the path.
        System.out.println("The shortest path from vertex " + start + " to vertex " + destination + " is:");
        while (!thePath.isEmpty()) {
            System.out.print(thePath.pop());
            if (!thePath.isEmpty())
                System.out.print(" -> ");
        }
        System.out.println(" (Distance = " + dist[destination] + ")");
    }
}
/*</listing>*/

I think it's a matter of how i display the variables and loop the program to count how many distances I need to find. Any help is appreciated. Thanks

[macosxnerd101]

You can store thePath.pop() in an int, and print out the corresponding element in the dist array as well.