Single-Source Shortest Paths
====================================================

.. _dijkstra_algo_main:

Dijkstra Algorithm
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Dijkstra algorithm is used to calculate single source shortest path problem. It can be implemented with BFS and a priority queue.

Take :numref:`dijkstra` as an example. To calculate the short path from source node 1 to the other nodes in the graph:

#. initialize a minium distance table with `INT_MAX`
#. put node 1 into a priority queue `pq` order by distance from node 1
#. get top node from `pq`, and skip it if it is in `visited` set
#. loop edges of top node, update the minium distance table, and add neighbor node into `pq`
#. add top node into `visited` set, repeat step 2 to 5 until `pq` is empty

.. figure:: dijkstra.png
  :align: center
  :name: dijkstra

  BFS + Priority Queue ordered by distance to single source

.. literalinclude:: dijkstra.h
  :linenos:
  :lines: 12-38
  :language: c++

Dijkstra algorithm greedily chooses which vertex to explore next, according to the value of priority(u) [priority(u) = distance(s,u)] - where `distance` is the cost so far.

.. code-block:: none
  :caption: priority(u) = distance(s,u)

  +---+           +---+           +---+
  | s | ========> | u | ------->  | t |
  +---+           +---+           +---+


Dijkstra’s algorithm is a Greedy algorithm and time complexity is O((V+E)LogV) (with the use of Fibonacci heap).

.. _beford:

Bellman Ford Algorithm
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Dijkstra doesn’t work for Graphs with negative weights, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for ``distributed systems``. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra. :numref:`Bellman_Ford_Algo` is a sample implementation.

.. code-block:: c++
  :name: Bellman_Ford_Algo
  :caption: Find shortest distances from src to all other vertices using Bellman-Ford algorithm. The function also detects negative weight cycle!

  void BellmanFord(struct Graph* graph, int src) {
      int V = graph->V, E = graph->E;
      // Step 1: Initialize distances from src to all other vertices as INT_MAX
      vector<int> dist(V, INT_MAX);
      dist[src] = 0;
      // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src to any other vertex can have at-most |V| - 1 edges
      for (int i = 1; i <= V - 1; i++) {
          for (int j = 0; j < E; j++) {
              int u = graph->edge[j].src, v = graph->edge[j].dest, weight = graph->edge[j].weight;
              if (dist[u] != INT_MAX and dist[u] + weight < dist[v])
                  dist[v] = dist[u] + weight;
          }
      }
      // Step 3: check for negative-weight cycles. The above step guarantees shortest distances if graph doesn't contain negative weight cycle. If we get a shorter path, there is a cycle.
      for (int i = 0; i < E; i++) {
          int u = graph->edge[i].src, v = graph->edge[i].dest, weight = graph->edge[i].weight;
          if (dist[u] != INT_MAX and dist[u] + weight < dist[v]) {
              return; // If negative cycle is detected, simply return
          }
      }
  }

The Kth iteration generates the shortest paths in K steps from src. :numref:`cheapest_flight` is an example where Bellman Ford is a better fit than Dijkstra.


A-Star Algorithm
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A-Star is basically an informed variation of Dijkstra. A-Star is considered as a ``BEST First Search`` because it greedily chooses which vertex to explore next, according to the value of priority(u) [priority(u) = heuristic(u,t) + distance(s,u)] - where `distance` is the cost so far.

.. code-block:: none
  :caption: priority(u) = distance(s,u) + heuristic(u,t)

  +---+           +---+           +---+
  | s | ========> | u | ------->  | t |
  +---+           +---+           +---+


.. only:: html

  A-star could be much faster with the heuristic's help.

  .. figure:: a-star-dijkstra.png
    :align: center
    :name: astar-dijkstra

    Path finding without obstacle

  .. figure:: a-star-dijkstra-obs.png
    :align: center
    :name: astar-dijkstra-obs

    Path finding with obstacles


  - https://www.youtube.com/watch?v=bRvs8rOQU-Q