dijkstra_greedy.cpp File Reference

Dijkstra algorithm implementation More...

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

Include dependency graph for dijkstra_greedy.cpp:

Go to the source code of this file.

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

Namespaces
namespace	greedy_algorithms
	for string class
namespace	greedy_algorithms::dijkstra
	Functions for the Dijkstra algorithm implementation.

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

Definition in file dijkstra_greedy.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 199 of file dijkstra_greedy.cpp.

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

tests()

void tests ( )

static

Self-test implementations.

Returns

void

Definition at line 160 of file dijkstra_greedy.cpp.

                    {
    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";
}