New to java.
What I am trying to make is a directed graph that represents a city. Most of the vertices are just streets but some are tourist sites which have weights (since one has to stay there for some time). I am working with Dijkstra's shortest path algorithm and has made some edition for adding the vertices' weights into it.
However, the problem occurs that when I set a vertex as a tour site and give it a weight, the vertex does not seem to have a weight at all when it is first visited. The weight then showed up when the vertex is visited the second time. I don't know where the problem has been, but I would guess it is somewhere that I am not directly editing the original variables.
The print out lines are marked below between * *. One is in calculateShortest(), another in calculateMin().
public class Graph
{
protected HashMap<Integer, GraphNode> ntable = new HashMap<Integer, GraphNode>();
//a hashmap of every node's edge treemap, in which edges are sorted according to weight of each
protected HashMap<Integer, TreeMap<Integer, GraphEdge>> etable = new HashMap<Integer, TreeMap<Integer,GraphEdge>>();
}
public class GraphNode
{
private int val;
private boolean site;
private boolean hotel;
private int time;
private int distance = Integer.MAX_VALUE;
private LinkedList<GraphNode> shortest = new LinkedList<GraphNode>();
}
public class GraphEdge implements Comparable<GraphEdge>
{
private int nd1;
private int nd2;
private int weight;
}
public class Path
{
protected LinkedList<GraphNode> path = new LinkedList<GraphNode>();
Graph g = new Graph();
GraphNode start = new GraphNode(0);
protected HashSet<GraphNode> settled = new HashSet<GraphNode>();
protected HashSet<GraphNode> unsettled = new HashSet<GraphNode>();
public Graph calculateShortest(int start)
{
g.ntable.get(start).setDist(0);
unsettled.add(g.ntable.get(start));
while (unsettled.size() != 0)
{
GraphNode current = getLowestCostNode(unsettled);
unsettled.remove(current);
TreeMap<Integer, GraphEdge> adjacentE = g.etable.get(current.getVal());
*
//printing out below shows vertex has no weight
System.out.println("Curr: "+ current.getVal() + " " + current.getSiteTime());
*
for (GraphEdge edge: adjacentE.values())
{
GraphNode adjacent = g.ntable.get(edge.getEnd());
int cost = edge.getWeight() + current.getSiteTime();
if (!settled.contains(adjacent))
{
calculateMin(adjacent, cost, current);
unsettled.add(adjacent);
}
}
settled.add(current);
}
return g;
}
public GraphNode getLowestCostNode(HashSet<GraphNode> unsettled)
{
GraphNode lowestDistNd = null;
int lowestDist = Integer.MAX_VALUE;
for (GraphNode nd : unsettled)
{
int nodeDist = nd.getDist();
if (nodeDist < lowestDist)
{
lowestDist = nodeDist;
lowestDistNd = nd;
}
}
return lowestDistNd;
}
public void calculateMin(GraphNode evaNd, int cost, GraphNode startNd)
{
int startDist = startNd.getDist();
if (startDist + cost < evaNd.getDist())
{
evaNd.setDist(startDist + cost);
LinkedList<GraphNode> shortest = new LinkedList<GraphNode>(startNd.getShortest());
shortest.add(startNd);
evaNd.setShortest(shortest);
*
//print out if the node's distance is changed
System.out.println("Change " + evaNd.getVal() + " " + evaNd.getDist());
*
}
}
}
Output of the line printing that shows problem (does not include main method output):
Curr: 1 0
Change: 2 10
Change: 3 15
Curr: 2 0
Change: 4 22
Change: 6 25
Curr: 3 0
Change: 5 25
Curr: 4 0 //1st time visiting shows no weight
Change: 6 23
Change: 5 24
Curr: 6 0
Curr: 5 0
Curr: 1 0
Curr: 2 0
Curr: 3 0
Curr: 4 30 //2nd time visiting shows weight
Curr: 6 0
Curr: 5 0
For every vertex, getDist() return the distance from the source vertex to itself, and getCost() return the distance plus the weight of the vertex.
My main method is below. The addNodeEdge() have been tested to work well. I am using an example(see photo below) from Dijkstra Algorithm in Java and ABCDEF is 123456 in my case. In addition to the graph, I am trying to make D (which is vertex 4) as a site with a weight of 30. Visualization of the graph
public static void main (String [] args){
Path p = new Path();
p.g.addNodeEdge(1, 2, 10);
p.g.addNodeEdge(1, 3, 15);
p.g.addNodeEdge(2, 4, 12);
p.g.addNodeEdge(2, 6, 15);
p.g.addNodeEdge(3, 5, 10);
p.g.addNodeEdge(4, 6, 1);
p.g.addNodeEdge(4, 5, 2);
p.g.addNodeEdge(6, 5, 5);
p.calculateShortest(1);
System.out.println(p.g.ntable.get(5).getDist());//print out 24
p.settled.clear();
p.unsettled.clear();
p.g.ntable.get(4).setSite(30);
p.calculateShortest(1);
System.out.println(p.g.ntable.get(5).getDist());//still print out 24
}
I would expect the shortest path to E (vertex 5) 30 and to F (vertex 6) 25 because the path through D (vertex 4) with a weight of 30 is too large. However, what I have got here after I changed D's weight is exactly the same before I added weight to D. Like I explained above, I think the problem is with D's weight changing... Any help would be great appreciated.
