.. _dijkstra:

Dijkstra
============

Dijkstra's Algorithm
--------------------

Dijkstra's algorithm finds the shortest paths from a source node to all other nodes in a weighted graph with non-negative edge weights. This algorithm uses a priority queue to always select the node with the minimum tentative distance.

**Input**: A weighted graph with non-negative weights, and a source node `s`  
**Output**: Shortest distances from `s` to all other nodes

Pseudocode
~~~~~~~~~~

.. code:: c++

    // Initialize distances
    vector<float> dist(n, INF);
    dist[s] = 0;

    priority_queue<pair<float, int>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        // Select node with minimum distance
        int u = pq.top().second; 
        float d = -pq.top().first;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        // Update distances to neighbors
        for (auto &[v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }

.. image:: /images/dijkstra.png

Working Example
~~~~~~~~~~~~~~~

Consider node `A` as the source. The algorithm proceeds as follows:

1. Initial distance: `A=0`, others=∞  
2. Process `A`, update neighbors `B=3`, `C=1`  
3. Select `C` (smallest distance), update neighbor `D=4`  
4. Select `B`, update neighbor `D=3`  
5. Select `D`, no updates remain  

Final distances: `A=0`, `B=3`, `C=1`, `D=3`

Proof of Correctness
~~~~~~~~~~~~~~~~~~~~

Using mathematical induction:  

- **Base case**: Distance to source is correctly 0  
- **Inductive step**: If all previous min selections were correct, then relaxing edges from the current node will yield correct distances  

At each step, the algorithm selects the node `u` with minimum confirmed distance and :math:`d_u + w(u, v)` updates the tentative distance for neighbor `v`.

Implementation Notes
~~~~~~~~~~~~~~~~~~~~

.. code:: c++

    struct Edge {
        int to;
        float weight;
    };

    vector<float> dijkstra(const vector<vector<Edge>> &adj, int s) {
        int n = adj.size();
        vector<float> dist(n, INF);
        dist[s] = 0;
        
        // Use min-heap (priority_queue as max-heap with negative weights)
        priority_queue<pair<float, int>> pq;
        pq.push({0, s});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            d = -d;
            
            // Skip processed nodes
            if (d > dist[u]) continue;  
            
            for (auto &[v, w] : adj[u]) {
                // Check if new path is better
                if (dist[v] > dist[u] + w) {  
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v}); 
                }
            }
        }
        return dist;
    }

- **Time complexity**: O((V+E) log V) using priority queue  
- **Space complexity**: O(V + E)

.. Problem Statement
   ------------

We have a directed weighted graph 
:math:`G`
. The weights of all edges of :math:`G` are non-negative.

Now we want to find, for each vertex, the length of the shortest path from vertex :math:`sc` to all other vertices, where the length of a path is equal to the sum of the weights of its edges.

Dijkstra's Algorithm
--------------------

We define an array called :math:`dis`. During algorithm execution, :math:`dis_u` represents the shortest path to vertex :math:`u` where the previous vertex in the path has definitely been selected (selection will be explained later). Initially, all elements of the :math:`dis` array are set to :math:`\infty`. First, we know :math:`dis_{sc} = 0`. Now we select :math:`sc` and update the :math:`dis` values of :math:`sc`'s neighboring vertices.

In each step of the algorithm, from among the vertices not yet selected, we choose the vertex with the minimal :math:`dis` value and name it :math:`v`.

We now prove that the length of the shortest path from :math:`sc` to :math:`v` is exactly the current value of :math:`dis_v`. For this proof, we use contradiction: assume there exists a shorter path (a path of length :math:`P`). Take the last selected vertex in this path and call it :math:`last` (it must exist since vertex :math:`sc` is selected). Name the next vertex after :math:`last` as :math:`u` (this next vertex must also exist since the final vertex wasn't selected yet).

By contradiction assumption, the path length to :math:`v` is less than :math:`dis_v`, and since edges have non-negative weights, the path length to :math:`u` is also less than :math:`dis_v`. Since the previous vertex of :math:`u` in the path was a selected vertex and the final distances of selected vertices are exactly their :math:`dis` values, then :math:`dis_u` at the time of selecting :math:`last` was equal to the shortest path length to :math:`u`. Given that :math:`dis_u < P` and :math:`P < dis_v`, we have :math:`dis_u < dis_v`, which contradicts the minimality of :math:`dis_v` among current values. Therefore, our initial assumption is false and the proof holds.

Now that we've proven :math:`dis_v` exactly equals the shortest path length to :math:`v`, we select it and then for all its neighbors like :math:`adj` where the edge from :math:`v` to :math:`adj` has weight :math:`w`, we perform:
:math:`dis_{adj} = min(dis_{adj}, dis_v + w)`.
We continue this process until all vertices are selected.

.. code-block:: python
   :linenos:

   def order_analysis(graph):
       # peymayesh graph va mohaseye order 
       order = len(graph.nodes())
       # bazgasht ehsas has order
       return order

Order Analysis
------------
There are two main approaches to implement this algorithm.

First Method with Order :math:`\mathcal{O}(n^2)`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In each step, we loop through all unselected vertices and find the minimum. In each step of the process, we perform :math:`\mathcal{O}(n)` operations. Since the algorithm has :math:`n` steps, the order of the program becomes :math:`\mathcal{O}(n^2)`.

The Second Method with Order :math:`\mathcal{O}(n + m.lg(n))`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

In each step, instead of iterating over all vertices, we use data structures that can find the minimum faster, such as :math:`set` and :math:`priority-queue` in :math:`C++`. (Assume we are using :math:`set` here.)

In each step, the minimum value of :math:`dis` can be found in :math:`\mathcal{O}(1)`. Each time we change the value of an entry in :math:`dis`, we must update it in the :math:`set`, which has an order of :math:`\mathcal{O}(lg(n))`.

Because in each step, the number of :math:`dis` entries that may change is equal to the number of neighbors of the selected vertex. Therefore, we change the values of :math:`dis` equal to the total number of neighbors of all vertices. We know the total number of neighbors is :math:`\mathcal{O}(m)`. Thus, the total time cost for updates is :math:`\mathcal{O}(m.log(n))`, resulting in an overall order of :math:`\mathcal{O}(n + m.lg(n))`.