Dijkstra's Algorithm

[Dark Rain]

We were asked to implement a weighted directed graph, and then perform dijkstra's algorithm on it. I have written this graph class:

#include "limits.h"
#include <iostream>
#include <iomanip>
#include <queue>
#include <functional>
#include <String>
using namespace std;

	class Graph
	{
	public: 
		// Enum
		enum { MAXIMUM = 20 };

		// Constructor
		Graph()
		{
			num_verticies = 0;
		}

		// Returns number of verticies in graph
		int size()
		{
			return num_verticies;
		}

		// Returns true if there is an edge from source to target
		bool is_edge(int source, int target)
		{
			bool edge = false;

			if (edges[source][target] > 0)
			{
				edge = true;
			}

			return edge;
		}

		// Returns true if label is defined as a vertex in the graph
		bool is_label(string label)
		{
			bool if_label = false;

			for (int i = 0; i < MAXIMUM; i++)
			{
				if (labels[i] == label)
				{
					if_label = true;
				}
			}

			return if_label;
		}

		// Returns the label for vertex
		string get_label(int vertex)
		{
			string label;

			if (vertex > MAXIMUM)
			{
				label = "Error";
			} else {
				label = labels[vertex];
			}

			return label;
		}

		// Returns the vertex number for label in graph
		int get_vertex_num(string label)
		{
			int vertex_num = -1;

			for (int i = 0; i < MAXIMUM; i++)
			{
				if (labels[i] == label)
				{
					vertex_num = i;
				}
			}

			return vertex_num;
		}

		// Adds a vertex with label to graph
		void add_vertex(string label)
		{
			int i; 

			for (i = 0; i < MAXIMUM; i++)
			{
				if (labels[i] == "empty")
				{
					labels[i] = label;
					num_verticies++;
					break;
				}

				if (labels[i] == label)
				{
					break;
				}
			}

			// Checks to see if all vertex space is filled up, if so a message
			// is printed, and no more verticies are added.
			if (i >= MAXIMUM)
			{
				cout << "Maximum number of verticies reached. \n";
				return;
			}
		}

		// Adds an edge from source to target with weight weight
		void add_edge(int source, int target, int weight)
		{
			edges[source][target] = weight;
		}

		// Removes an edge from source to target
		void remove_edge(int source, int target)
		{
			edges[source][target] = 0;
		}

		// Gets weight of edge from source to target
		int get_weight(int source, int target)
		{
			return edges[source][target];
		}

		// Initializes both arrays
		void initialize_arrays()
		{
			for (int i = 0; i < MAXIMUM; i++)
			{
				for (int j = 0; j < MAXIMUM; j++)
				{
					edges[i][j] = 0;
				}

				labels[i] = "empty";
			}
		}

		// Print arrays
		void print_arrays()
		{
			for (int i = 0; i < MAXIMUM; i++)
			{
				for (int j = 0; j < MAXIMUM; j++)
				{
					cout << setw(3) << edges[i][j];
					cout << " ";
				}

				cout << "\n";
			}

			cout << "\n\n";

			for (int i = 0; i < MAXIMUM; i++)
			{
				cout << labels[i] << "\n";
			}
		}

		// Initializes distance and predecessor arrays
		void initialize_single_source()
		{
			for (int i = 0; i < MAXIMUM; i++)
			{
				distance[i] = INT_MAX;
				predecessor[i] = NULL;
			}

			distance[0] = 0;
		}

		// Relaxes edges
		void relax(int source, int target, int weight)
		{
			if (distance[target] > (distance[source] + get_weight(source, target)))
			{
				distance[target] = distance[source] + get_weight(source, target);
				predecessor[target] = source;
			}
		}

		// Dijkstra's algorithm
		void dijkstra(int source, int target, int weight)
		{
			int j = 0;

			initialize_single_source();

			for (int i = 0; i < MAXIMUM; i++)
			{
				queue.push(labels[i]);
			}

			while (queue != NULL)
			{
				set[j] = queue.top;
			}

		}
	private:
		int edges[MAXIMUM][MAXIMUM];
		int distance[MAXIMUM];
		int predecessor[MAXIMUM];
		string labels[MAXIMUM];
		string set[MAXIMUM];
		priority_queue<int, vector<int>, greater<int> > queue;
		int num_verticies;
	};

The dijkstra's algorithm function is not finished yet, because I'm not sure where to go with it. The pseudo-code we received in class is as follows:

Dijkstra(G, w, s)
1. initialize_single_source(G, s)
2. S <-- empty
3. Q <-- V[G]
4. while Q != empty
5. do u <-- extract-min(Q)
6. S <-- S union {u}
7. for each vertex adjacent to u
8. do relax(u, v, w)

The thing I don't get is how to find vertices adjacent to u. I could use the is_edge function to find out if an edge is there, but how would I go about finding a target for the function?

Also, I'm not too sure how the min-queue is going to work if it has no weights to go by, the weights are given in a file and read in another class.

[nspils]

when I implemented this, I had an "Edge" node which stored both start and end vertices and the "weight" of that edge. This is put into the priority queue.

The manner in which you implement your graph provides you the mechanism of finding adjacent vertices ... does the phrase "adjacency list" ring any bells? Have your array or list of vertices, each of which hold a list of its own - being the edges adjacent to that vertice. You now have a collection of edge nodes which make it very easy to identify each one.