Dijkstra (Matrix graph representation)

DijkstraMatrixRep.cpp

#include <iostream>
#include <limits>

// ref: http://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/

using namespace std;

#define V 9

/* Recursive print. */
void printPath(int dst, int parents[V]) {
	if (parents[dst] == -1) {
		cout << dst;
		return;
	}

	printPath(parents[dst], parents);
	cout << "," << dst;
}

void printPaths(int d[V], int parents[V]) {
	cout <<  "Vertex\tWeight\tPath" << endl;
	for (int i = 0 ; i < V ; i++) {
		cout << i << "\t" << d[i] << "\t";
		
		printPath(i, parents);
		cout << endl;
	}
}

int nextMin(bool visit[V], int d[V]) {
	int min;
	int min_weight = INT_MAX;
	
	for (int v=0 ; v < V ; v++) {
		if (!visit[v] && min_weight >= d[v]) {
			min = v;
			min_weight = d[v];
		}		
	}
	
	return min;
}

void dijkstra(int graph[V][V], int src) {
	bool visit[V];
	int d[V];
	int parent[V];
	
	// init structures
	for (int i=0 ; i < V ; i++) {
		visit[i] = false;
		d[i] = INT_MAX;
		parent[i] = -1;
	}
	
	d[src] = 0;

	for (int counter=0 ; counter < V ; counter++) {
		int u = nextMin(visit, d);
		visit[u] = true;

		for (int v=0 ; v < V ; v++) {
			if (!visit[v] && graph[u][v] && d[v] > d[u]+graph[u][v]) {
				d[v] = d[u]+graph[u][v];
				parent[v] = u;
			}
		}
	}
	
	printPaths(d, parent);
}

int main() {
	int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 0, 10, 0, 2, 0, 0},
                       {0, 0, 0, 14, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}
                      };

	dijkstra(graph,0);

	return 0;
}