# Dijkstra's Algorithm

Page 1 of 1

## 1 Replies - 10868 Views - Last Post: 21 April 2011 - 01:05 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=228700&amp;s=ff89be426fb55a674c87d184fd4ce9b2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 jcs224

Reputation: 0
• Posts: 26
• Joined: 23-October 09

# Dijkstra's Algorithm

Posted 21 April 2011 - 12:09 PM

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.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(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

Is This A Good Question/Topic? 0

## Replies To: Dijkstra's Algorithm

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,173
• Joined: 27-December 08

## Re: Dijkstra's Algorithm

Posted 21 April 2011 - 01:05 PM

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