greedy_algorithms::dijkstra Namespace Reference

Functions for the Dijkstra algorithm implementation. More...

Classes
class	Graph
	Wrapper class for storing a graph. More...

Functions
int	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	print (std::vector< int > dist, int V)
	Utility function to print the distances to vertices.
void	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.

Detailed Description

Functions for the Dijkstra algorithm implementation.

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:

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

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