dijkstra.cpp File Reference

[Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path)] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) More...

#include <cassert>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <utility>
#include <vector>

Include dependency graph for dijkstra.cpp:

Namespaces
namespace	graph
	Graph Algorithms.

Functions
void	graph::addEdge (std::vector< std::vector< std::pair< int, int > > > *adj, int u, int v, int w)
	Function that add edge between two nodes or vertices of graph.
int	graph::dijkstra (std::vector< std::vector< std::pair< int, int > > > *adj, int s, int t)
	Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source.
void	tests ()
int	main ()

Variables
constexpr int64_t	INF = std::numeric_limits<int64_t>::max()

Detailed Description

[Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path)] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

Author

Ayaan Khan

Dijkstra's Algorithm is used to find the shortest path from a source vertex to all other reachable vertex in the graph. The algorithm initially assumes all the nodes are unreachable from the given source vertex so we mark the distances of all vertices as INF (infinity) from source vertex (INF / infinity denotes unable to reach).

in similar fashion with BFS we assume the distance of source vertex as 0 and pushes the vertex in a priority queue with it's distance. we maintain the priority queue as a min heap so that we can get the minimum element at the top of heap

Basically what we do in this algorithm is that we try to minimize the distances of all the reachable vertices from the current vertex, look at the code below to understand in better way.

Function Documentation

main()

int main

(

void

)

Main function

           {
    // running predefined tests
    tests();
 
    int vertices = int(), edges = int();
    std::cout << "Enter the number of vertices : ";
    std::cin >> vertices;
    std::cout << "Enter the number of edges : ";
    std::cin >> edges;
 
    std::vector<std::vector<std::pair<int, int>>> adj(
        vertices, std::vector<std::pair<int, int>>());
 
    int u = int(), v = int(), w = int();
    while (edges--) {
        std::cin >> u >> v >> w;
        graph::addEdge(&adj, u, v, w);
    }
 
    int s = int(), t = int();
    std::cin >> s >> t;
    int dist = graph::dijkstra(&adj, s - 1, t - 1);
    if (dist == -1) {
        std::cout << "Target not reachable from source" << std::endl;
    } else {
        std::cout << "Shortest Path Distance : " << dist << std::endl;
    }
    return 0;
}

Here is the call graph for this function:

tests()

void tests

(

)

Function to test the Algorithm

             {
    std::cout << "Initiatinig Predefined Tests..." << std::endl;
    std::cout << "Initiating Test 1..." << std::endl;
    std::vector<std::vector<std::pair<int, int>>> adj1(
        4, std::vector<std::pair<int, int>>());
    graph::addEdge(&adj1, 1, 2, 1);
    graph::addEdge(&adj1, 4, 1, 2);
    graph::addEdge(&adj1, 2, 3, 2);
    graph::addEdge(&adj1, 1, 3, 5);
 
    int s = 1, t = 3;
    assert(graph::dijkstra(&adj1, s - 1, t - 1) == 3);
    std::cout << "Test 1 Passed..." << std::endl;
 
    s = 4, t = 3;
    std::cout << "Initiating Test 2..." << std::endl;
    assert(graph::dijkstra(&adj1, s - 1, t - 1) == 5);
    std::cout << "Test 2 Passed..." << std::endl;
 
    std::vector<std::vector<std::pair<int, int>>> adj2(
        5, std::vector<std::pair<int, int>>());
    graph::addEdge(&adj2, 1, 2, 4);
    graph::addEdge(&adj2, 1, 3, 2);
    graph::addEdge(&adj2, 2, 3, 2);
    graph::addEdge(&adj2, 3, 2, 1);
    graph::addEdge(&adj2, 2, 4, 2);
    graph::addEdge(&adj2, 3, 5, 4);
    graph::addEdge(&adj2, 5, 4, 1);
    graph::addEdge(&adj2, 2, 5, 3);
    graph::addEdge(&adj2, 3, 4, 4);
 
    s = 1, t = 5;
    std::cout << "Initiating Test 3..." << std::endl;
    assert(graph::dijkstra(&adj2, s - 1, t - 1) == 6);
    std::cout << "Test 3 Passed..." << std::endl;
    std::cout << "All Test Passed..." << std::endl << std::endl;
}

Here is the call graph for this function: