Dijkstra’s algorithm

Dijkstra’s algorithm finds shortest paths from a given vertex to all the other in a graph with non-negative edge weights.

Input

v e s
a b c (e times)
...

v – number of vertices
e – number of edges
s – start vertex
a b c – edge between a and b with weight c

Sample input

Output

The algorithm returns shortest distances from city s to all other cities.

Complexity

Implementation of priority queue is important as we need to find the closest vertex (to s) |V| times. Also we need to be able to update item value, but std::priority_queue doesn’t support decrease_key operation.

In my solution as a priority queue I use std::set, which is most often implemented as red-black tree, so all operations are O(logn), therefore decrease_key and push are O(logn). According to this algorithm runs in:

O(|V|·log|V| + |E|·log|V|) = O(log|V| · (|V| + |E|))

Source code

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
#include <climits>
 
using namespace std;
 
struct Edge
{
    Edge(int to, int cost)
    {
        this->to = to;
        this->cost = cost;
    }
 
    int to;
    int cost;
};
 
struct Vertex
{
    int id;
    long long minCost;
    vector<Edge> edges;
 
    bool operator<(const Vertex &other) const
    { 
        if (minCost == other.minCost)
            return id < other.id;
 
        return minCost < other.minCost; 
    }
};
 
 
//PRIORITY QUEUE
struct CompareNode
{
    bool operator()(const Vertex* lhs, const Vertex* rhs) const
    {
        return *lhs < *rhs;
    }
};
set<Vertex*, CompareNode> tree;
 
void push(Vertex* v)
{
    tree.insert(v);
}
 
void decrease_key(Vertex* v)
{
    set<Vertex*, CompareNode>::iterator it = tree.find(v);
    if (it != tree.end())
        tree.erase(it);
    push(v);
}
 
Vertex* pop()
{
    Vertex* v = *tree.begin();
    tree.erase(tree.begin());
    return v;
}
 
bool empty()
{
    return tree.empty();
}
//=========================================================================
 
int main()
{
    int v, e, s;
    scanf("%d %d %d", &v, &e, &s);
 
    //VERTICES
    Vertex * vertices = new Vertex[v];
    for (int i = 0; i < v; i++)
    {
        vertices[i].id = i;
        vertices[i].minCost = LONG_MAX;     
    }   
 
    //EDGES
    int a, b, c;
    for (int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        vertices[a - 1].edges.push_back(Edge(b - 1, c));
        vertices[b - 1].edges.push_back(Edge(a - 1, c));
    }
 
 
    //DIJKSTRA
    vertices[s - 1].minCost = 0;
    push(&vertices[s - 1]);
 
    Vertex* current;
    long long newCost;
    while (!empty())
    {
        current = pop();
 
        for (vector<Edge>::iterator it = current->edges.begin(); it != current->edges.end(); it++)
        {
            newCost = vertices[current->id].minCost + it->cost;
 
            if (vertices[it->to].minCost > newCost)
            {                           
                vertices[it->to].minCost = newCost;
                decrease_key(&vertices[it->to]);
            }
        }
    }
 
    //RESULT
    for (int i = 1; i < v; i++)
        printf("%ld ", vertices[i].minCost);
 
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <stdio.h>

#include <set>

#include <vector>

#include <algorithm>

#include <climits>

using namespace std;

struct Edge

{

Edge(int to, int cost)

{

this->to = to;

this->cost = cost;

}

int to;

int cost;

};

struct Vertex

{

int id;

long long minCost;

vector<Edge> edges;

bool operator<(const Vertex &other) const

{

if (minCost == other.minCost)

return id < other.id;

return minCost < other.minCost;

}

};

//PRIORITY QUEUE

struct CompareNode

{

bool operator()(const Vertex* lhs, const Vertex* rhs) const

{

return *lhs < *rhs;

}

};

set<Vertex*, CompareNode> tree;

void push(Vertex* v)

{

tree.insert(v);

}

void decrease_key(Vertex* v)

{

set<Vertex*, CompareNode>::iterator it = tree.find(v);

if (it != tree.end())

tree.erase(it);

push(v);

}

Vertex* pop()

{

Vertex* v = *tree.begin();

tree.erase(tree.begin());

return v;

}

bool empty()

{

return tree.empty();

}

//=========================================================================

int main()

{

int v, e, s;

scanf("%d %d %d", &v, &e, &s);

//VERTICES

Vertex * vertices = new Vertex[v];

for (int i = 0; i < v; i++)

{

vertices[i].id = i;

vertices[i].minCost = LONG_MAX;

}

//EDGES

int a, b, c;

for (int i = 0; i < e; i++)

{

scanf("%d %d %d", &a, &b, &c);

vertices[a - 1].edges.push_back(Edge(b - 1, c));

vertices[b - 1].edges.push_back(Edge(a - 1, c));

}

//DIJKSTRA

vertices[s - 1].minCost = 0;

push(&vertices[s - 1]);

Vertex* current;

long long newCost;

while (!empty())

{

current = pop();

for (vector<Edge>::iterator it = current->edges.begin(); it != current->edges.end(); it++)

{

newCost = vertices[current->id].minCost + it->cost;

if (vertices[it->to].minCost > newCost)

{

vertices[it->to].minCost = newCost;

decrease_key(&vertices[it->to]);

}

//RESULT

for (int i = 1; i < v; i++)

printf("%ld ", vertices[i].minCost);

return 0;

}