Dijkstra’s shortest path algorithm - Summary

https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/lec20/lec20.htm

This code implicitly divides the set of vertices into three sets:

1. The completed vertices: visited vertices that have already been removed from the queue.
2. The frontier: visited vertices on the queue
3. The unvisited vertices: everything else

Except for the initial vertex v₀, the vertices in set 2 are always neighbors of vertices in set 1. Thus, the queued vertices form a frontier in the graph, separating sets 1 and 3. The expand function moves a frontier vertex into the completed set and then expands the frontier to include any previously unseen neighbors of the new frontier vertex.

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

 procedure UniformCostSearch(Graph, start, goal)
  node ← start
  cost ← 0
  frontier ← priority queue containing node only
  explored ← empty set
  do
    if frontier is empty
      return failure
    node ← frontier.pop()
    if node is goal
      return solution
    explored.add(node)
    for each of node's neighbors n
      if n is not in explored
          frontier.add(n)

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://java2blog.com/dijkstra-java/
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-in-java-using-priorityqueue/

Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph.

    private int dist[];

    private Set<Integer> settled;

    private PriorityQueue<Node> pq;

    private int V; // Number of vertices

    List<List<Node> > adj;

  

    public DPQ(int V)

    {

        this.V = V;

        dist = new int[V];

        settled = new HashSet<Integer>();

        pq = new PriorityQueue<Node>(V, new Node());

    }

  

    // Funtion for Dijkstra's Algorithm

    public void dijkstra(List<List<Node> > adj, int source)

    {

        this.adj = adj;

  

        for (int i = 0; i < V; i++)

            dist[i] = Integer.MAX_VALUE;

  

        // Add source node to the priority queue

        pq.add(new Node(source, 0));

  

        // Distance to the source is 0

        dist = 0;

        while (settled.size() != V) {

  

            // remove the minimum distance node 

            // from the priority queue 

            int u = pq.remove().node;

  

            // adding the node whose distance is

            // finalized

            settled.add(u);

  

            e_Neighbours(u);

        }

    }

  

    // Function to process all the neighbours 

    // of the passed node

    private void e_Neighbours(int u)

    {

        int edgeDistance = -1;

        int newDistance = -1;

  

        // All the neighbors of v

        for (int i = 0; i < adj.get(u).size(); i++) {

            Node v = adj.get(u).get(i);

  

            // If current node hasn't already been processed

            if (!settled.contains(v.node)) {

                edgeDistance = v.cost;

                newDistance = dist[u] + edgeDistance;

  

                // If new distance is cheaper in cost

                if (newDistance < dist[v.node])

                    dist[v.node] = newDistance;

  

                // Add the current node to the queue

                pq.add(new Node(v.node, dist[v.node]));

            }

        }

    }




Greedy Algorithms | Set 7 (Dijkstra’s shortest path algorithm)
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Dijkstra's algorithm is agraph search algorithm that solves the single-sourceshortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

Time complexity:  (where  is the number of edges) is due to (Fredman & Tarjan 1984). This isasymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.


http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph.
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (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 minimum distance from source.

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


We use a boolean array sptSet[] to represent the set of vertices included in SPT. If a value sptSet[v] is true, then vertex v is included in SPT, otherwise not. Array dist[] is used to store shortest distance values of all vertices.
4) Time Complexity of the implementation is O(V^2). If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap

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.

4) Time Complexity of the implementation is O(V^2). If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap. We will soon be discussing O(E Log V) algorithm as a separate post.

5) Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman–Ford algorithm can be used.

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

     bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest

                     // path tree or shortest distance from src to i is finalized

     // Initialize all distances as INFINITE and stpSet[] as false

     for (int i = 0; i < V; i++)

        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] != INT_MAX

                                       && dist[u]+graph[u][v] < dist[v])

            dist[v] = dist[u] + graph[u][v];

     }

     // print the constructed distance array

     printSolution(dist, V);

}

// 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;

}

http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed. It is possible to adapt Dijkstra's algorithm to handle negative weight edges by combining it with the Bellman-Ford algorithm (to remove negative edges and detect negative cycles), such an algorithm is called Johnson's algorithm.

In fact, Dijkstra's explanation of the logic behind the algorithm,namely

Problem 2. Find the path of minimum total length between two given nodes  and .

We use the fact that, if  is a node on the minimal path from  to , knowledge of the latter implies the knowledge of the minimal path from  to .

http://www.algolist.com/code/java/Dijkstra%27s_algorithm
Adjacency List+BFS+MinHeap
class Vertex implements Comparable<Vertex> { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } } public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } } public static List<Vertex> getShortestPathTo(Vertex target) { List<Vertex> path = new ArrayList<Vertex>(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } }
http://cs.fit.edu/~ryan/java/programs/graph/Dijkstra-java.html

1 public class Dijkstra {
  2 
  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    }
 53 }

Greedy Algorithms | Set 8 (Dijkstra’s Algorithm for Adjacency List Representation)
The time complexity for the matrix representation is O(V^2).
Adjacency List Representation: O(ELogV)
http://massivealgorithms.blogspot.com/2014/07/greedy-algorithms-set-8-dijkstras.html
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.

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);

}

https://stackoverflow.com/questions/6952660/java-priority-queue-reordering-when-editing-elements?lq=1

A straightforward idea is to remove and then add the changed node. Do not do that as remove()takes O(n). Instead, insert another entry for the same node into the PriorityQueue, and ignore duplicates when polling the queue, i.e. do something like:

PriorityQueue<Step> queue = new PriorityQueue();

void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());

    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }

}

Edit: It is not advisable to change the priorities of elements in the PQ, hence the need to insert Steps instead of Nodes.

https://gabormakrai.wordpress.com/tag/fibonacci-heap/
Using Fibonacci heap for the Priority Queue can be decrease the running time, because it has θ(1) amortized cost on Decrease key and insert operations compared to the θ(lgn) Decrease key operation of binary heap. 

https://stackoverflow.com/questions/6952660/java-priority-queue-reordering-when-editing-elements?lq=1

You can avoid updating items in the queue just marking each node as visited=false by default, and adding new items to the queue as you go.

Then pop a node from the queue and process it only if it was not visited before.

Dijkstra's algorithm guarantees that each node is visited only once, so even if you may have stale nodes down the queue you never really process them.

Also it's probably easier if you separate the algorithm internals from the graph data structure.

https://www.quora.com/What-is-the-significance-of-using-a-priority-queue-in-Dijkstras-algorithm-What-difference-does-it-make-if-we-use-a-normal-queue

In Dijkstra's algorithm, the important step is selecting an unexplored vertex v such that there is an edge (u, v) in the graph, where u is an already explored vertex, and d'(v) = dist(u) + cost(u, v) is minimum. Here, dist(u) is the length of the already found shortest path from the source vertex s to vertex u, and cost(u, v) is the weight of the edge from u to v.

If we store the unexplored vertices in a simple array/linked list, we would have to iterate over the whole list each time to find the desired vertex v, with minimum d'(v) (d'(v) = dist(u) + cost(u, v)).

If we store the vertices in a priority queue with d'(v) as the key for each vertex, we can get the vertex with minimum d'(v) by using the Extract-Min operation. If we use a binary (min-)heap, the asymptotic complexity of Extract-Minoperation will be O(log n).

After selecting vertex v, and updating dist(v), we may find that we have a shorter path to another unexplored vertex w through v, i.e. a path with cost d'(w) = dist(v) + cost(v, w), which is less than the cost of the existing path to w.

This vertex will be in the priority queue, and its key value will need to be changed to the new value using the Decrease-Key operation, which will decrease the key of a certain element, and bubble it up if necessary to ensure the min-heap property. A binary (min-)heap will support doing Decrease-Keyoperation with O(log n) complexity.

Again, if we had used a simple list, this step would have required us to iterate over the whole list to update the key of a vertex.

Also, there are other data structures that can be used to implement a priority queue more efficiently, such as binomial heaps and Fibonacci heaps. But these come at the expense of added complexity.

Read full article from Greedy Algorithms | Set 7 (Dijkstra’s shortest path algorithm)