###Do not visit a node twice###
Do not visit a node twice
###Starting set###
Starting set
###Sample modifications###
Sample modifications
###Do not visit a node twice###
###Starting set###
###Sample modifications###
Do not visit a node twice
Starting set
Sample modifications
What this means is that if the pq already contains a particular vertex, the "decrease priority" function will move that vertex within the pq by decreasing its value. For example, if vertex 1 has cost 10, and then you want to decrease its cost to 3, the decrease keypriority function will move/reinsert the vertex into the correct place in the pq.
What this means is that if the pq already contains a particular vertex, the "decrease priority" function will move that vertex within the pq by decreasing its value. For example, if vertex 1 has cost 10, and then you want to decrease its cost to 3, the decrease key will move/reinsert the vertex into the correct place in the pq.
What this means is that if the pq already contains a particular vertex, the "decrease priority" function will move that vertex within the pq by decreasing its value. For example, if vertex 1 has cost 10, and then you want to decrease its cost to 3, the decrease priority function will move/reinsert the vertex into the correct place in the pq.
###Do not visit a node twice###
Your function needs to track whether a vertex has been visited before, and prevent it from being visited twice. In the wikipedia article, that requirement is mentioned in a comment here:
for each neighbor v of u: // only v that is still in Q
Another difference is that the wikipedia article assumes that the pq (priority queue) has a "decrease priority" function:
Q.decrease_priority(v, alt)
What this means is that if the pq already contains a particular vertex, the "decrease priority" function will move that vertex within the pq by decreasing its value. For example, if vertex 1 has cost 10, and then you want to decrease its cost to 3, the decrease key will move/reinsert the vertex into the correct place in the pq.
If you don't have a decrease priority function, you can just add multiple copies of the same vertex into the pq (which is what you are doing). For example, you can insert "vertex 1 cost 10" into the pq, and later insert "vertex 1 cost 3" into the pq, knowing that the cost 3 node will be pulled out of the pq first. The problem is that later on, you will pull "vertex 1 cost 10" out of the pq. But if you tracked the visited vertices, you will be able to ignore this "out of date" pq node.
###Starting set###
You prepopulate your priority queue with every vertex, with each vertex having infinite distance except for the source vertex, which has 0 distance. Actually, you only need to prepopulate your priority queue with the source vertex. If any of the other vertices are reachable, they will eventually be added to the priority queue.
###Sample modifications###
Here is your code with modifications mentioned above:
private static int improvedDijkstra(int source, ArrayList<Road>[] adj) {
PriorityQueue<Node> vertices = new PriorityQueue<>();
int [] dist = new int [adj.length];
int [] prev = new int [adj.length];
bool[] visited = new bool[adj.length];
dist[source] = 0;
for (int i = 0; i < adj.length; i++) {
if (i != source) {
dist[i] = Integer.MAX_VALUE;
prev[i] = Integer.MAX_VALUE;
}
}
// Start with source node only.
vertices.add(new Node(source, 0));
while (!vertices.isEmpty()) { //O(n)
Node u = vertices.poll(); //this should have O(logn)
if (visited[u.value])
continue;
visited[u.value] = true;
for(Road v: adj[u.value]) {
// No need to connect to vertices already visited.
if (visited[v.end])
continue;
int alt = dist[u.value] + v.distance;
if (alt < dist[v.end]) {
dist[v.end] = alt;
prev[v.end] = alt;
vertices.add(new Node(v.end, alt)); //this should have O(logn)
}
}
}
}