shotest path code help
Hi, i am stuck with this piece of code, not sure how to finish it up. Have modyfied as per requirement, but Still 2 more parts to add:
1) Enteingr a node identifier, such as "F" when prompted.
2) To see the path from the specified node back to the START node.
The user enters "exit" to halt the process. This prog. expects an input file that specifies a directed graph's edges. To show u more clearly, i have provided a sample at the end of the code as documentation.
Thanks.
import java.util.*;
import java.io.*;
public class SP {
public static void main(String[ ] args) {
if (args.length < 1) {
System.err.println("SP <file with edges>");
return;
}
SP self = new SP();
self.readFile(args[0]);
self.buildGraph();
self.sp();
}
private void readFile(String filename) {
edges = new TreeSet();
try {
BufferedReader input = new BufferedReader(new FileReader(filename));
String record = null;
while ((record = input.readLine()) != null) {
String[ ] edge_list = record.split("\\s");
for (int i = 0; i < edge_list.length; i++)
edges.add(edge_list);
}
input.close();
}
catch(Exception e) { System.exit(-1); }
}
private void buildGraph() {
nodes = new TreeMap();
Iterator it = edges.iterator();
while (it.hasNext()) {
String next = (String) it.next();
if (next.length() > 2)
putNode(next.substring(0,1), // from
next.substring(1,2), // to
next.substring(2)); // weight
}
}
private void putNode(String f, String t, String w) {
Node from = getNode(f);
if (startNode == null ) startNode = from;
Node to = getNode(t);
from.addAdjacentNode(to, Integer.parseInt(w));
}
private Node getNode(String id) {
Node n = null;
if (!nodes.containsKey(id)) nodes.put(id, n = new Node(id));
else n = (Node) nodes.get(id);
return n;
}
private void sp() {
Iterator it = nodes.values().iterator();
int[ ] distances = new int[nodes.values().size()];
int i = 0;
//*** Initialize the distances array and add START to allowed list
while (it.hasNext()) {
Node next = (Node) it.next();
next.setIndex(i);
if (next == startNode) {
distances = 0; // START's weight to itself is 0
next.setPicked(true); // START has been picked for "allowed list"
}
else
distances = INF; // otherwise, distance to is INFinity
i++;
}
//*** Conduct the search
Node current = startNode;
while (true) {
updateDistances(current, distances);
Node next = pickNextNode(nodes.values().iterator(), distances);
if (next == null) break; // search is over
next.setPicked(true);
current = next;
}
//*** Print the shortest paths from start
System.out.println("Shortest distances from " + startNode.getId());
it = nodes.values().iterator();
while (it.hasNext()) {
Node next = (Node) it.next();
System.out.println(" to " + next.getId() + " is " + next.getDistanceTo());
}
}
private void updateDistances(Node node, int[ ] distances) {
//*** Find neighbors of current node and update distances from current.
Set neighbors = node.getAdjacentNodes();
Iterator it = neighbors.iterator();
while (it.hasNext()) {
WeightedEdge next = (WeightedEdge) it.next();
Node to = next.getTo();
if (to.getPicked()) continue; // if already picked, continue
//*** Test whether the new path to a node is cheaper.
int weight_to = node.getDistanceTo() + next.getWeight();
int ind = to.getIndex();
if (weight_to < distances[ind]) {
distances[ind] = weight_to;
to.setDistanceTo(weight_to);
}
}
}
private Node pickNextNode(Iterator it, int[ ] distances) {
Node node = null;
int best = INF;
for (int i = 0; i < distances.length; i++) {
Node next = (Node) it.next();
if (next.getPicked()) continue;
if (distances < best) {
best = distances;
node = next;
}
}
return node;
}
private Map nodes;
private Set edges;
private Stack stack;
private static boolean dumpFlag;
private Node startNode;
public static final int INF = Integer.MAX_VALUE;
}
class WeightedEdge {
public WeightedEdge(Node n, int w) {
to = n; weight = w;
}
public Node getTo() { return to; }
public int getWeight() { return weight; }
private Node to;
private int weight;
}
class Node {
public Node(String id) {
this.id = id;
adjacent_nodes = new HashSet();
}
public void addAdjacentNode(Node n, int w) {
if (n != null) adjacent_nodes.add(new WeightedEdge(n, w));
}
public Set getAdjacentNodes() {
return adjacent_nodes;
}
public void setIndex(int i) { index = i; }
public int getIndex() { return index; }
public void setDistanceTo(int d) { distance_to = d; }
public int getDistanceTo() { return distance_to; }
public void setPicked(boolean yes_no) { picked = yes_no; }
public boolean getPicked() { return picked; }
public String getId() { return id; }
private Set adjacent_nodes;
private String id;
private boolean picked;
private int distance_to;
private int index;
}
//*** Input file:
// AB2 AF9 BC8 BD15 BF6 CD1 EC7 ED3 FE3
//*** Output from execution:
// Shortest distances from A
// to A is 0
// to B is 2
// to C is 10
// to D is 11
// to E is 11
// to F is 8
