Dijkstra's algorithm

From Algorithmist
(Redirected from Dijkstra's Algorithm)
Jump to: navigation, search
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[edit]

The algorithm is as follows, starting from source S:

  1. Set distance to 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.
    2. Relax V - Adjust all adjacent vertices

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
    2. add vertex to 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[edit]

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[edit]

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.
}