# Dijkstra's algorithm

 This is a stub or unfinished. Contribute by editing me.

Dijkstra's algorithm is a greedy algorithm for calculating the single source shortest path for a graph. It can also be used to calculate the shortest path spanning tree.

## Algorithm

The algorithm is as follows, starting from source ${\displaystyle S}$:

1. Set distance to ${\displaystyle S}$ to 0.
2. While there is a node to be relaxed
1. Find the node V that is the closest to S that is not relaxed.

Time complexity of the following algorithm is O(M log N), where M is number of edges and N is number of vertices. Dijkstra can also be implemented as O(n * log (n) + m) using a fibonacci heap, which can be faster, especially with dense graphs.

UM[x] is the total distance between the first vertex and x. S shows which vertices are selected before. A is our matrix that shows the distances. For example, A[i][j] is the distance between i and j.

1. for(all the vertices except the first vertex)
1. UM[j] = A[first vertex][j]
2. UM[first vertex] = 0
3. CLEAR(S)
4. while(our target vertex doesn't exist in S)
1. vertex = vertex with minimum distance that doesn't exist in S
3. for(all the vertices that don't exist in S)
1. if(UM[vertex] + A[vertex][current vertex] < UM[current vertex])
1. UM[current vertex] = UM[vertex] + A[vertex][current vertex];

## C++ Implementation

O(m * log(n))

The data structure used here is an adjacency list for a weighted graph.

vector <vector< pair <int, int> > > edges: edges [A] [it] contains all edges: pair < price to go from A to B, B>

```#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> Dijkstra(vector< vector< pair<int, int> > > edges, int startPoint) {
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > sortedEdges; //minimum priority queue.
vector<int> shortestPath;
for(int i = 0; i < edges.size(); i++) shortestPath.push_back(-1);
shortestPath[startPoint] = 0;
for(int i = 0; i < edges[startPoint].size(); i++) sortedEdges.push(edges[startPoint][i]);
while(sortedEdges.size() != 0)
{
auto current = sortedEdges.top();
sortedEdges.pop();
if(shortestPath[current.second] == -1)
{
shortestPath[current.second] = current.first; //The shortest path has been found to current.second
for(int i = 0; i < edges[current.second].size(); i++)
{
pair<int, int> newBridge;
newBridge.first = current.first + edges[current.second][i].first; //PRICE
newBridge.second = edges[current.second][i].second;
sortedEdges.push(newBridge);
}
}
}
return shortestPath; //shortestPath[endPoint] = result; If -1 no path.
}
```

## C++ Implementation with custom struct

O(m * log(n))

```#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Edge
{
int from; //Node A (not required)
int to; //Node B
int price; //Price to go from A to B
Edge(int _from, int _to, int _price) : from(_from), to(_to), price(_price) {}
};

inline bool operator< (const Edge& lhs, const Edge& rhs) {
return lhs.price > rhs.price; //Sort it from smallest to largest
}

vector<int> Dijkstra(vector< vector<Edge> > edges, int startPoint) {
priority_queue<Edge> sortedEdges; //minimum priority queue.
vector<int> shortestPath;
for(int i = 0; i < edges.size(); i++) shortestPath.push_back(-1);
shortestPath[startPoint] = 0;
for(int i = 0; i < edges[startPoint].size(); i++) sortedEdges.push(edges[startPoint][i]);
while(sortedEdges.size() != 0)
{
auto currentEdge = sortedEdges.top();
sortedEdges.pop();
if(shortestPath[currentEdge.to] == -1)
{
shortestPath[currentEdge.to] = currentEdge.price; //The shortest path has been found to current.second
for(int i = 0; i < edges[currentEdge.to].size(); i++)
{
Edge newBridge = edges[currentEdge.to][i];
newBridge.price += currentEdge.price;
sortedEdges.push(newBridge);
}
}
}
return shortestPath; //shortestPath[endPoint] = result; If -1 no path.
}
```