Dijkstra

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:

graph结构类似adjacency list。

我没有用heap，所以时间复杂度应该是$V^2$.

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
struct AdjListNode
{
    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
        edges[src].emplace_back(AdjListNode(dest, weight));
        // Un-directed graph, set dest to src Edge too
        edges[dest].emplace_back(AdjListNode(src, weight));    
    }    

    const int V;
    vector<vector<AdjListNode>> edges;
};

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);
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 7, 8);
    graph.addEdge(1, 2, 8);
    graph.addEdge(1, 7, 11);
    graph.addEdge(2, 3, 7);
    graph.addEdge(2, 8, 2);
    graph.addEdge(2, 5, 4);
    graph.addEdge(3, 4, 9);
    graph.addEdge(3, 5, 14);
    graph.addEdge(4, 5, 10);
    graph.addEdge(5, 6, 2);
    graph.addEdge(6, 7, 1);
    graph.addEdge(6, 8, 6);
    graph.addEdge(7, 8, 7);

    vector<int> dist = dijkstra(graph, 0);

    for(int i=0; i<V; i++){
        cout<<i<<' '<<dist[i]<<endl;
    }

}