Dijkstra's Algorithm


Greedy Algorithms | Set 8 (Dijkstra’s Algorithm for Adjacency List Representation) | GeeksforGeeks
Related: Geeksforgeeks - Dijkstra’s shortest path algorithm
X. Proof
https://www.cs.dartmouth.edu/~thc/cs10/lectures/0509/0509.html

Correctness of Dijkstra's algorithm

How do we know that, at termination (when the min-priority queue is empty because every vertex has been dequeued), v.dist is in fact the shortest-path weight for every vertex v? We rely on a loop invariant argument. We state a property that pertains to a loop, which we call the loop invariant, and we have to show three things about it:
  1. The loop invariant is true before we enter the loop.
  2. If the loop invariant is true upon starting an iteration of the loop, it remains true upon starting the next iteration.
  3. The loop invariant, combined with the reason that we exit the loop, yields the property that we want to show.
To make our loop invariant a little simpler, let's adopt a notation for all vertices not in the min-priority queue at a given time; we'll call these vertices set S. Then here is the loop invariant:
At the start of each iteration of the while-loop, v.dist is the correct shortest-path weight for each vertex v in S.
It's easy to see that the loop invariant holds before the first iteration. At that time, all vertices are in the min-priority queue, and so set S is empty. Therefore, the loop invariant holds vacuously.
Next, let's see how the third part helps. When we exit the loop, the min-priority queue is empty, and so the set S consists of all the vertices. Therefore, every vertex has its correct shortest-path weight.
The hardest part is the second part, where we have to show that each iteration maintains the truth of the loop invariant. We'll give a simplified version of the reasoning. (A formal proof is a bit more involved.) Assume that as we enter an iteration of this loop, all vertices in set S have their correct shortest-path weights in their dist values. Then every edge leaving these vertices has been examined in some relaxation step. Consider the vertex u in the min-priority queue with the lowest dist value. Its dist value can never again decrease. Why not? Because the only edges remaining to be relaxed are edges leaving vertices in the min-priority queue and every vertex in the min-priority queue has a dist value at least as large as u.dist. Since all edge weights are nonnegative, we must have u.dist  ≤  v.dist + w(v,u) for every vertex v in the min-priority queue, and so no future relaxation will decrease u.dist. Therefore, u.dist is as low as it can go, and we can extract vertex u from the min-priority queue and relax all edges leaving u. That is, u.dist has its correct shortest-path weight and it is now in set S.
https://zh.coursera.org/lecture/algorithms/063dijkstrasuan-fa-de-zheng-ming-cNUJU
https://blog.csdn.net/softee/article/details/39034129
2. 算法正确性证明

上一节描述的Dijkstra算法把图中的结点分为两个部分，分别标记为VISITED和UNVISITED，使用S和V-S来表示。为证明的方便，区分了S和V-S中的点的距离函数，分别为D和D_est，V-S中的距离函数被称为估值函数。算法的主要操作是循环执行第3到5步。证明算法的正确性，可以通过证明每次循环执行之前，S和V-S中的结点满足以下3条属性，执行之后依然满足。

属性1. S中任意m的点的的路径长度D[m]就是其最短路径。

属性2. 估值函数满足下述条件：


也就是说，对于V-S中的任意结点n，其估值路径D_est[n]是其只通过S中结点的最短路径。

属性3. V-S中估值最小的点n，D_est[n]的值就是其最短路径。

算法第一步S={s}，只包含出发结点，且D[s]=0，故而满足属性1，更新相邻结点之后，容易证明，也满足属性2。属性3则需要证明，过程如下。

证明：假设D_est[n]不是n的最短路径，因为D_est是只通过S中结点的最短路径，所以结点n的真实的最短路径必然会经过集合S之外的结点，设路径上第一个非S中的点为j。则真实的最短路径的形式为s->...->j->...->n。因为假设了j之前的点都是S中的，所以根据属性2，D_est[j] < =D[n] < D_est[n]，与n是估值最小的结点矛盾，所以属性成立。

算法接下来的操作是把n加入S，并试图更新V-S中结点的距离估值，容易证明，3-5步的一次操作之后，属性1-3仍然满足，所以得证。
https://blog.csdn.net/HappyRocking/article/details/79250099

Dijkstra’s algorithm: The time complexity for the matrix representation is O(V^2),  O(ELogV) for adjacency list representation.
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate aSPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.
Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSet and has minimum distance value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.


With adjacency list representation, all vertices of a graph can be traversed in O(V+E) time using BFS. The idea is to traverse all vertices of graph using BFS and use a Min Heap to store the vertices not yet included in SPT (or the vertices for which shortest distance is not finalized yet).  Min Heap is used as a priority queue to get the minimum distance vertex from set of not yet included vertices. Time complexity of operations like extract-min and decrease-key value is O(LogV) for Min Heap.

1) Create a Min Heap of size V where V is the number of vertices in the given graph. Every node of min heap contains vertex number and distance value of the vertex.
2) Initialize Min Heap with source vertex as root (the distance value assigned to source vertex is 0). The distance value assigned to all other vertices is INF (infinite).
3) While Min Heap is not empty, do following
…..a) Extract the vertex with minimum distance value node from Min Heap. Let the extracted vertex be u.
…..b) For every adjacent vertex v of u, check if v is in Min Heap. If v is in Min Heap and distance value is more than weight of u-v plus distance value of u, then update the distance value of v.

Time Complexity: The time complexity of the above code/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS). The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV)
Note that the above code uses Binary Heap for Priority Queue implementation. Time complexity can be reduced to O(E + VLogV) using Fibonacci Heap. The reason is, Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(Logn) time.
1) The code calculates shortest distance, but doesn’t calculate the path information. We can create a parent array, update the parent array when distance is updated (like prim’s implementation) and use it show the shortest path from source to different vertices.
2) The code is for undirected graph, same dijekstra function can be used for directed graphs also.
3) The code finds shortest distances from source to all vertices. If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target (Step 3.a of algorithm).
4) Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman–Ford algorithm can be used, we will soon be discussing it as a separate post.
http://rosettacode.org/wiki/Dijkstra's_algorithm
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Kind of looks like BFS - but update each node's distance
1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // Initialization
3      for each vertex v in Graph:           
4          if v ≠ source
5              dist[v] ← infinity                          // Unknown distance from source to v
6              prev[v] ← undefined                         // Predecessor of v
7          end if
8          Q.add_with_priority(v, dist[v])
9      end for 
10
11     while Q is not empty:                         // The main loop
12         u ← Q.extract_min()                         // Remove and return best vertex
13         for each neighbor v of u:             // only v that is still in Q
14             alt = dist[u] + length(u, v) 
15             if alt < dist[v]
16                 dist[v] ← alt
17                 prev[v] ← u
18                 Q.decrease_priority(v, alt)
19             end if
20         end for
21     end while
22     return dist[], prev[]

void dijkstra(struct Graph* graph, int src)
{
    int V = graph->V;// Get the number of vertices in graph
    int dist[V];      // dist values used to pick minimum weight edge in cut
    // minHeap represents set E
    struct MinHeap* minHeap = createMinHeap(V);
    // Initialize min heap with all vertices. dist value of all vertices
    for (int v = 0; v < V; ++v)
    {
        dist[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v, dist[v]);
        minHeap->pos[v] = v;
    }
    // Make dist value of src vertex as 0 so that it is extracted first
    minHeap->array[src] = newMinHeapNode(src, dist[src]);
    minHeap->pos[src]   = src;
    dist[src] = 0;
    decreaseKey(minHeap, src, dist[src]);
    // Initially size of min heap is equal to V
    minHeap->size = V;
    // In the followin loop, min heap contains all nodes
    // whose shortest distance is not yet finalized.
    while (!isEmpty(minHeap))
    {
        // Extract the vertex with minimum distance value
        struct MinHeapNode* minHeapNode = extractMin(minHeap);
        int u = minHeapNode->v; // Store the extracted vertex number
        // Traverse through all adjacent vertices of u (the extracted
        // vertex) and update their distance values
        struct AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl != NULL)
        {
            int v = pCrawl->dest;
            // If shortest distance to v is not finalized yet, and distance to v
            // through u is less than its previously calculated distance
            if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
                                          pCrawl->weight + dist[u] < dist[v])
            {
                dist[v] = dist[u] + pCrawl->weight;
                // update distance value in min heap also
                decreaseKey(minHeap, v, dist[v]);
            }
            pCrawl = pCrawl->next;
        }
    }
    // print the calculated shortest distances
    printArr(dist, V);
}
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};
struct AdjList
{
    struct AdjListNode *head;  // pointer to head node of list
};
struct Graph
{
    int V;
    struct AdjList* array;
};
http://www.cs.fsu.edu/~baker/pc/city/dijkstra.pdf
http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java
class Graph {
   private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
 
   /** One edge of the graph (only used by Graph constructor) */
   public static class Edge {
      public final String v1, v2;
      public final int dist;
      public Edge(String v1, String v2, int dist) {
         this.v1 = v1;
         this.v2 = v2;
         this.dist = dist;
      }
   }
 
   /** One vertex of the graph, complete with mappings to neighbouring vertices */
   public static class Vertex implements Comparable<Vertex> {
      public final String name;
      public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
      public Vertex previous = null;
      public final Map<Vertex, Integer> neighbours = new HashMap<>();
 
      public Vertex(String name) {
         this.name = name;
      }
 
      private void printPath() {
         if (this == this.previous) {
            System.out.printf("%s", this.name);
         } else if (this.previous == null) {
            System.out.printf("%s(unreached)", this.name);
         } else {
            this.previous.printPath();
            System.out.printf(" -> %s(%d)", this.name, this.dist);
         }
      }
 
      public int compareTo(Vertex other) {
         return Integer.compare(dist, other.dist);
      }
   }
 
   /** Builds a graph from a set of edges */
   public Graph(Edge[] edges) {
      graph = new HashMap<>(edges.length);
 
      //one pass to find all vertices
      for (Edge e : edges) {
         if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
         if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
      }
 
      //another pass to set neighbouring vertices
      for (Edge e : edges) {
         graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
         //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
      }
   }
 
   /** Runs dijkstra using a specified source vertex */ 
   public void dijkstra(String startName) {
      if (!graph.containsKey(startName)) {
         System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
         return;
      }
      final Vertex source = graph.get(startName);
      NavigableSet<Vertex> q = new TreeSet<>();
 
      // set-up vertices
      for (Vertex v : graph.values()) {
         v.previous = v == source ? source : null;
         v.dist = v == source ? 0 : Integer.MAX_VALUE;
         q.add(v);
      }
 
      dijkstra(q);
   }
 
   /** Implementation of dijkstra's algorithm using a binary heap. */
   private void dijkstra(final NavigableSet<Vertex> q) {      
      Vertex u, v;
      while (!q.isEmpty()) {
 
         u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
         if (u.dist == Integer.MAX_VALUE) break; //continue??? we can ignore u (and any other remaining vertices) since they are unreachable
 
         //look at distances to each neighbour
         for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
            v = a.getKey(); //the neighbour in this iteration
 
            final int alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist) { // shorter path to neighbour found
               q.remove(v);//\\
               v.dist = alternateDist;
               v.previous = u;//\\
               q.add(v);//\\
            } 
         }
      }
   }
}
http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html
Dijkstra's algorithm to find shortest path from s to all other nodes
  3    // Dijkstra's algorithm to find shortest path from s to all other nodes
  4    public static int [] dijkstra (WeightedGraph G, int s) {
  5       final int [] dist = new int [G.size()];  // shortest known distance from "s"
  6       final int [] pred = new int [G.size()];  // preceeding node in path
  7       final boolean [] visited = new boolean [G.size()]; // all false initially
  8 
  9       for (int i=0; i<dist.length; i++) {
 10          dist[i] = Integer.MAX_VALUE;
 11       }
 12       dist[s] = 0;
 13 
 14       for (int i=0; i<dist.length; i++) {
 15          final int next = minVertex (dist, visited);
 16          visited[next] = true;
 17 
 18          // The shortest path to next is dist[next] and via pred[next].
 19 
 20          final int [] n = G.neighbors (next);
 21          for (int j=0; j<n.length; j++) {
 22             final int v = n[j];
 23             final int d = dist[next] + G.getWeight(next,v);
 24             if (dist[v] > d) {
 25                dist[v] = d;
 26                pred[v] = next;
 27             }
 28          }
 29       }
 30       return pred;  // (ignore pred[s]==0!)
 31    }
 32 
 33    private static int minVertex (int [] dist, boolean [] v) {
 34       int x = Integer.MAX_VALUE;
 35       int y = -1;   // graph not connected, or no unvisited vertices
 36       for (int i=0; i<dist.length; i++) {
 37          if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
 38       }
 39       return y;
 40    }
 41 
 42    public static void printPath (WeightedGraph G, int [] pred, int s, int e) {
 43       final java.util.ArrayList path = new java.util.ArrayList();
 44       int x = e;
 45       while (x!=s) {
 46          path.add (0, G.getLabel(x));
 47          x = pred[x];
 48       }
 49       path.add (0, G.getLabel(s));
 50       System.out.println (path);
 51    }
Using Priority Queue
http://www.sanfoundry.com/java-program-mplement-dijkstras-algorithm-using-priority_queue/
  1.     public void dijkstra_algorithm(int adjacency_matrix[][], int source)
  2.     {
  3.         int evaluationNode;
  4.         for (int i = 1; i <= number_of_nodes; i++)
  5.             for (int j = 1; j <= number_of_nodes; j++)
  6.                 adjacencyMatrix[i][j] = adjacency_matrix[i][j];
  7.  
  8.         for (int i = 1; i <= number_of_nodes; i++)
  9.         {
  10.             distances[i] = Integer.MAX_VALUE;
  11.         }
  12.  
  13.         priorityQueue.add(new Node(source, 0));
  14.         distances[source] = 0;
  15.         while (!priorityQueue.isEmpty())
  16.         {
  17.             evaluationNode = getNodeWithMinimumDistanceFromPriorityQueue();
  18.             settled.add(evaluationNode);
  19.             evaluateNeighbours(evaluationNode);
  20.         }
  21.     } 
  22.  
  23.     private int getNodeWithMinimumDistanceFromPriorityQueue()
  24.     {
  25.         int node = priorityQueue.remove();
  26.         return node;
  27.     }
  28.  
  29.     private void evaluateNeighbours(int evaluationNode)
  30.     {
  31.         int edgeDistance = -1;
  32.         int newDistance = -1;
  33.  
  34.         for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
  35.         {
  36.             if (!settled.contains(destinationNode))//\\
  37.             {
  38.                 if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
  39.                 {
  40.                     edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
  41.                     newDistance = distances[evaluationNode] + edgeDistance;
  42.                     if (newDistance < distances[destinationNode])
  43.                     {
  44.                         distances[destinationNode] = newDistance;
  45.                     }
  46.                     priorityQueue.add(new Node(destinationNode,distances[destinationNode]));
  47.                 }   
  48.             }
  49.         }
  50.     }
http://www.ideserve.co.in/learn/dijkstra-shortest-path-algorithm
Given a graph with no negative distance between any two vertices, find the shortest distance between initial vertex 0 and all vertices.

http://en.literateprograms.org/index.php?title=Special:DownloadCode/Dijkstra%27s_algorithm_(Java)&oldid=15444
// visited[]?
 21 class Vertex implements Comparable<Vertex>
 22 {
 23     public final String name;
 24     public Edge[] adjacencies;
 25     public double minDistance = Double.POSITIVE_INFINITY;
 26     public Vertex previous;
 27     public Vertex(String argName) { name = argName; }
 28     public String toString() { return name; }
 29     public int compareTo(Vertex other)
 30     {
 31         return Double.compare(minDistance, other.minDistance);
 32     }
 34 }
 37 class Edge
 38 {
 39     public final Vertex target;
 40     public final double weight;
 41     public Edge(Vertex argTarget, double argWeight)
 42     { target = argTarget; weight = argWeight; }
 43 }
 47     public static void computePaths(Vertex source)
 48     {
 49         source.minDistance = 0.;
 50         PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
 51  vertexQueue.add(source);
 52 
 53  while (!vertexQueue.isEmpty()) {
 54      Vertex u = vertexQueue.poll();
 55 
 56             // Visit each edge exiting u
 57             for (Edge e : u.adjacencies)
 58             {
 59                 Vertex v = e.target;
 60                 double weight = e.weight;
 61                 double distanceThroughU = u.minDistance + weight;
 62   if (distanceThroughU < v.minDistance) {
 63       vertexQueue.remove(v);//\\
 64 
 65       v.minDistance = distanceThroughU ;
 66       v.previous = u;//\\
 67       vertexQueue.add(v);//\\
 68   }
 69             }
 70         }
 71     }
 72 
 73     public static List<Vertex> getShortestPathTo(Vertex target)
 74     {
 75         List<Vertex> path = new ArrayList<Vertex>();
 76         for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
 77             path.add(vertex);
 78 
 79         Collections.reverse(path);
 80         return path;
 81     }
http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
      对于一个有向图或无向图，所有边权为正（边用邻接矩阵的形式给出），给定a和b，求a到b的最短路，保证a一定能够到达b。这条最短路是否一定存在呢？答案是肯定的。相反，最长路就不一定了，由于边权为正，如果遇到有环的时候，可以一直在这个环上走，因为要找最长的，这样就使得路径越变越长，永无止境，所以对于正权图，在可达的情况下最短路一定存在，最长路则不一定存在。这里先讨论正权图的最短路问题。
      最短路满足最优子结构性质，所以是一个动态规划问题。最短路的最优子结构可以描述为：
      D(s, t) = {Vs ... Vi ... Vj ... Vt}表示s到t的最短路，其中i和j是这条路径上的两个中间结点，那么D(i, j)必定是i到j的最短路，这个性质是显然的，可以用反证法证明。
      基于上面的最优子结构性质，如果存在这样一条最短路D(s, t) = {Vs ... Vi Vt}，其中i和t是最短路上相邻的点，那么D(s, i) = {Vs ... Vi} 必定是s到i的最短路。Dijkstra算法就是基于这样一个性质，通过最短路径长度递增，逐渐生成最短路。
      Dijkstra算法是最经典的最短路算法，用于计算正权图的单源最短路（Single Source Shortest Path，源点给定，通过该算法可以求出起点到所有点的最短路），它是基于这样一个事实：如果源点到x点的最短路已经求出，并且保存在d[x] ( 可以将它理解为D(s, x) )上，那么可以利用x去更新 x能够直接到达的点 的最短路。即：
      d[y] = min{ d[y], d[x] + w(x, y) }           y为x能够直接到达的点，w(x, y) 则表示x->y这条有向边的边权
      具体算法描述如下：对于图G = <V, E>，源点为s，d[i]表示s到i的最短路，visit[i]表示d[i]是否已经确定(布尔值)。
      1) 初始化 所有顶点 d[i] = INF, visit[i] = false，令d[s] = 0；
      2) 从所有visit[i]为false的顶点中找到一个d[i]值最小的，令x = i; 如果找不到，算法结束；
      3) 标记visit[x] = true, 更新和x直接相邻的所有顶点y的最短路： d[y] = min{ d[y], d[x] + w(x, y) }
     （第三步中如果y和x并不是直接相邻，则令w(x, y) = INF）
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
Matrix - O(V^2)
class ShortestPath
{
    // A utility function to find the vertex with minimum distance value,
    // from the set of vertices not yet included in shortest path tree
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        // Initialize min value
        int min = Integer.MAX_VALUE, min_index=-1;
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }
        return min_index;
    }
    // Funtion that implements Dijkstra's single source shortest path
    // algorithm for a graph represented using adjacency matrix
    // representation
    void dijkstra(int graph[][], int src)
    {
        int dist[] = new int[V]; // The output array. dist[i] will hold
                                 // the shortest distance from src to i
        // sptSet[i] will true if vertex i is included in shortest
        // path tree or shortest distance from src to i is finalized
        Boolean sptSet[] = new Boolean[V];
        // Initialize all distances as INFINITE and stpSet[] as false
        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
        // Distance of source vertex from itself is always 0
        dist[src] = 0;
        // Find shortest path for all vertices
        for (int count = 0; count < V-1; count++)
        {
            // Pick the minimum distance vertex from the set of vertices
            // not yet processed. u is always equal to src in first
            // iteration.
            int u = minDistance(dist, sptSet);
            // Mark the picked vertex as processed
            sptSet[u] = true;
            // Update dist value of the adjacent vertices of the
            // picked vertex.
            for (int v = 0; v < V; v++)
                // Update dist[v] only if is not in sptSet, there is an
                // edge from u to v, and total weight of path from src to
                // v through u is smaller than current value of dist[v]
                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }
        // print the constructed distance array
        printSolution(dist, V);
    }
}
http://www.codebytes.in/2015/11/dijkstras-algorithm-using-fibonacci.html
It's a heap data structure that can be used as a priority queue. It is the best priority queue in theory, considering the running times for operations like

findMinimum  O(1),
decreaseKey  O(1),
deleteMin       O(log n),
insert             O(1).

http://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/
Printing Paths in Dijkstra’s Shortest Path Algorithm
The idea is to create a separate array parent[]. Value of parent[v] for a vertex v stores parent vertex of v in shortest path tree. Parent of root (or source vertex) is -1. Whenever we find shorter path through a vertex u, we make u as parent of current vertex.
Once we have parent array constructed, we can print path using below recursive function.
void printPath(int parent[], int j)
{
    // Base Case : If j is source
    if (parent[j]==-1)
        return;

    printPath(parent, parent[j]);

    printf("%d ", j);
}

// A utility function to find the vertex with minimum distance
// value, from the set of vertices not yet included in shortest
// path tree
int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}
// Function to print shortest path from source to j
// using parent array
void printPath(int parent[], int j)
{
    // Base Case : If j is source
    if (parent[j]==-1)
        return;
    printPath(parent, parent[j]);
    printf("%d ", j);
}
// A utility function to print the constructed distance
// array
int printSolution(int dist[], int n, int parent[])
{
    int src = 0;
    printf("Vertex\t  Distance\tPath");
    for (int i = 1; i < V; i++)
    {
        printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src);
        printPath(parent, i);
    }
}
// Funtion that implements Dijkstra's single source shortest path
// algorithm for a graph represented using adjacency matrix
// representation
void dijkstra(int graph[V][V], int src)
{
    int dist[V];  // The output array. dist[i] will hold
                  // the shortest distance from src to i
    // sptSet[i] will true if vertex i is included / in shortest
    // path tree or shortest distance from src to i is finalized
    bool sptSet[V];
    // Parent array to store shortest path tree
    int parent[V];
    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < V; i++)
    {
        parent[0] = -1;
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    // Distance of source vertex from itself is always 0
    dist[src] = 0;
    // Find shortest path for all vertices
    for (int count = 0; count < V-1; count++)
    {
        // Pick the minimum distance vertex from the set of
        // vertices not yet processed. u is always equal to src
        // in first iteration.
        int u = minDistance(dist, sptSet);
        // Mark the picked vertex as processed
        sptSet[u] = true;
        // Update dist value of the adjacent vertices of the
        // picked vertex.
        for (int v = 0; v < V; v++)
            // Update dist[v] only if is not in sptSet, there is
            // an edge from u to v, and total weight of path from
            // src to v through u is smaller than current value of
            // dist[v]
            if (!sptSet[v] && graph[u][v] &&
                dist[u] + graph[u][v] < dist[v])
            {
                parent[v]  = u;
                dist[v] = dist[u] + graph[u][v];
            } 
    }
    // print the constructed distance array
    printSolution(dist, V, parent);
}

http://stackoverflow.com/questions/1871253/updating-java-priorityqueue-when-its-elements-change-priority
You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has been inserted. A TreeMap has the same limitation (as does a HashMap, which also breaks when the hashcode of its elements changes after insertion).

Read full article from Greedy Algorithms | Set 8 (Dijkstra’s Algorithm for Adjacency List Representation) | GeeksforGeeks
at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts