# Description:

Dijkstra's original algorithm does not use a min-priority queue and runs in time { O(|V|^{2})} O(|V|^{2}) (where { |V|} |V| is the number of nodes). The idea of this algorithm is also given in Leyzorek et al. 1957. The implementation based on a min-priority queue implemented by a Fibonacci heap and running in {O(|E|+|V|\log |V|)} O(|E|+|V|\log |V|) (where { |E|} |E| is the number of edges) is due to Fredman & Tarjan 1984. This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

## Example:

``````Note
``````

# Idea:

1. visited set to track visited nodes.
2. dist vector record the distance from each node to the root. first set dist[i] = infinity, except for dist[root], which = 0. set root to be next_to_visit

Loop until all is visited, or dist[next_to_visit]==infinity:

1. get the unvisited node, which has smallest dist[node], insert to visited.
2. update node' neighbors dist, if dist[neighbor] > dist[node] + weight of edge(node, neighbor).
3. extract next_to_visit, which should be unvisited and has the smallest dist

# Code:

``````#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

// A structure to represent a node in adjacency list
{
AdjListNode(int d, int w): dest(d), weight(w) {}
int dest;
int weight;
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
class Graph{
public:
Graph() = delete;
Graph(int n): V(n), edges(n) {}

void addEdge(int src, int dest, int weight){
// src to dest Edge
// Un-directed graph, set dest to src Edge too
}

const int V;
};

int minDistUnvisited(const vector<int>& dist, const unordered_set<int>& visited){
int min_dist=INT_MAX;
int min_ind;
for(int i=0; i<dist.size(); ++i){
if(visited.find(i)==visited.end() && dist[i]<=min_dist){
min_dist = dist[i];
min_ind = i;
}
}
return min_ind;
}

vector<int> dijkstra(const Graph & graph, int root){
unordered_set<int> visited;
vector<int> dist(graph.V, INT_MAX);

dist[root] = 0;
int next_v = root;

while(visited.size()!=graph.V && dist[next_v]!=INT_MAX){
visited.insert(next_v);

for(int i=0; i<graph.edges[next_v].size(); ++i){
int neighbor = graph.edges[next_v][i].dest;
int neighbor_weight = graph.edges[next_v][i].weight;
// if neighbor is unvisited, update
if(visited.find(neighbor)==visited.end()){
if(dist[neighbor] > dist[next_v]+neighbor_weight){
dist[neighbor] = dist[next_v]+neighbor_weight;
}
}

}
next_v = minDistUnvisited(dist, visited);
}

return dist;
}

int main(){
// create the graph given in above fugure
int V = 10;
// struct Graph* graph = createGraph(V);
Graph graph(V);