> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/graph/shortest-path/dijkstra-algorithm.md).

# Dijkstra Algorithm

## Problem Statement

Given a weighted, undirected and connected graph of **V** vertices and an adjacency list adj where adj\[i] is a list of lists containing two integers where the **first** integer of each list **j** denotes there is **edge** between i and j , second integers corresponds to the **weight** of that  edge . You are given the source vertex **S** and You to Find the shortest distance of all the vertex's from the source vertex **S**. You have to return a list of integers denoting shortest distance between **each node** and Source vertex **S**.\
 

**Note:** The Graph doesn't contain any negative weight cycle.

 

**Example 1:**

<pre><code><strong>Input:
</strong><strong>V = 2
</strong><strong>adj [] = {{{1, 9}}, {{0, 9}}}
</strong><strong>S = 0
</strong><strong>Output:
</strong>0 9
<strong>Explanation:
</strong>
The source vertex is 0. Hence, the shortest 
distance of node 0 is 0 and the shortest 
distance from node 1 is 9.
</code></pre>

&#x20;

**Example 2:**

<pre><code><strong>Input:
</strong><strong>V = 3, E = 3
</strong><strong>adj = {{{1, 1}, {2, 6}}, {{2, 3}, {0, 1}}, {{1, 3}, {0, 6}}}
</strong><strong>S = 2
</strong><strong>Output:
</strong>4 3 0
<strong>Explanation:
</strong>
For nodes 2 to 0, we can follow the path-
2-1-0. This has a distance of 1+3 = 4,
whereas the path 2-0 has a distance of 6. So,
the Shortest path from 2 to 0 is 4.
The shortest distance from 0 to 1 is 1 .
</code></pre>

&#x20;

**Your Task:**\
You don't need to read input or print anything. Your task is to complete the function **dijkstra()**  which takes the number of vertices V and an adjacency list adj as input parameters and Source vertex S returns a list of integers, where ith integer denotes the shortest distance of the ith node from the Source node. Here adj\[i] contains a list of lists containing two integers where the first integer j denotes that there is an edge between i and j and the second integer w denotes that the weight between edge i and j is w.

## Intuition

```
Take All edges and Relax

Time Complexity = ElogV
```

### Links

<https://practice.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1>

### Video Links

<https://www.youtube.com/watch?v=rp1SMw7HSO8&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
 vector <int> dijkstra(int V, vector<vector<int>> adj[], int s){
        vector<int> distance(V,INT_MAX);
        // Distance, node
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
        pq.push({0,s});
        distance[s] = 0;

        while (!pq.empty()) {
            int node = pq.top().second;

            for(auto &it: adj[node]){
                if(distance[node] + it[1] < distance[it[0]]){
                    int new_dis = distance[node] + it[1];
                    distance[it[0]] = new_dis;
                    pq.push({new_dis, it[0]});
                }
            }
            pq.pop();
        }
        
        for(int i = 0; i < V; i++) {
            if(distance[i] == INT_MAX)
                distance[i] = -1;
        }
        return distance;
    }
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###