dijkstra.cpp File Reference

Dijkstra algorithm implementation More...

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

Include dependency graph for dijkstra.cpp:

Classes
class	greedy_algorithms::dijkstra::Graph
	Wrapper class for storing a graph. More...

Namespaces
namespace	greedy_algorithms
	for std::vector

Functions
int	greedy_algorithms::dijkstra::minimum_distance (std::vector< int > mdist, std::vector< bool > vset, int V)
	Utility function that finds the vertex with the minimum distance in mdist.
void	greedy_algorithms::dijkstra::print (std::vector< int > dist, int V)
	Utility function to print the distances to vertices.
void	greedy_algorithms::dijkstra::dijkstra (Graph graph, int src)
	The main function that finds the shortest path from a given source to all other vertices using Dijkstra's Algorithm.
static void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Dijkstra algorithm implementation

Quote from Wikipedia.

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Author

David Leal

Arpan Jain

Function Documentation

dijkstra()

void greedy_algorithms::dijkstra::dijkstra	(	Graph	graph,
		int	src )

The main function that finds the shortest path from a given source to all other vertices using Dijkstra's Algorithm.

Note

This doesn't work on negative weights.

Parameters

graph	the graph to be processed
src	the source of the given vertex

Returns

void

                                    {
    int V = graph.vertexNum;
    std::vector<int> mdist{};  // Stores updated distances to the vertex
    std::vector<bool> vset{};  // `vset[i]` is true if the vertex `i` is included in the shortest path tree
 
    // Initialize `mdist and `vset`. Set the distance of the source as zero
    for (int i = 0; i < V; i++) {
        mdist[i] = INT_MAX;
        vset[i] = false;
    }
 
    mdist[src] = 0;
 
    // iterate to find the shortest path
    for (int count = 0; count < V - 1; count++) {
        int u = minimum_distance(mdist, vset, V);
 
        vset[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (!vset[v] && graph.edges[u][v] &&
                mdist[u] + graph.edges[u][v] < mdist[v]) {
                mdist[v] = mdist[u] + graph.edges[u][v];
            }
        }
    }
 
    print(mdist, V);
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    tests();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

minimum_distance()

int greedy_algorithms::dijkstra::minimum_distance	(	std::vector< int >	mdist,
		std::vector< bool >	vset,
		int	V )

Utility function that finds the vertex with the minimum distance in mdist.

Parameters

mdist	array of distances to each vertex
vset	array indicating inclusion in the shortest path tree
V	the number of vertices in the graph

Returns

index of the vertex with the minimum distance

                                                                        {
    int minVal = INT_MAX, minInd = 0;
    for (int i = 0; i < V; i++) {
        if (!vset[i] && (mdist[i] < minVal)) {
            minVal = mdist[i];
            minInd = i;
        }
    }
 
    return minInd;
}

Here is the call graph for this function:

print()

void greedy_algorithms::dijkstra::print	(	std::vector< int >	dist,
		int	V )

Utility function to print the distances to vertices.

This function prints the distances to each vertex in a tabular format. If the distance is equal to INT_MAX, it is displayed as "INF".

Parameters

dist	An array representing the distances to each vertex.
V	The number of vertices in the graph.

Returns

void

                                       {
    std::cout << "\nVertex  Distance\n";
    for (int i = 0; i < V; i++) {
        if (dist[i] < INT_MAX) {
            std::cout << i << "\t" << dist[i] << "\n";
        }
        else {
            std::cout << i << "\tINF" << "\n";
        }
    }
}

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

                    {
    greedy_algorithms::dijkstra::Graph graph(8);
 
    // 1st test.
    graph.add_edge(6, 2, 4);
    graph.add_edge(2, 6, 4);
 
    assert(graph.edges[6][2] == 4);
 
    // 2nd test.
    graph.add_edge(0, 1, 1);
    graph.add_edge(1, 0, 1);
 
    assert(graph.edges[0][1] == 1);
 
    // 3rd test.
    graph.add_edge(0, 2, 7);
    graph.add_edge(2, 0, 7);
    graph.add_edge(1, 2, 1);
    graph.add_edge(2, 1, 1);
 
    assert(graph.edges[0][2] == 7);
 
    // 4th test.
    graph.add_edge(1, 3, 3);
    graph.add_edge(3, 1, 3);
    graph.add_edge(1, 4, 2);
    graph.add_edge(4, 1, 2);
    graph.add_edge(2, 3, 2);
 
    assert(graph.edges[1][3] == 3);
 
    std::cout << "All tests have successfully passed!\n";
}