Dijkstra's Algorithm


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Dijkstra's Algorithm

  1. #1
    Join Date
    Sep 2005
    Posts
    74

    Dijkstra's Algorithm

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

    Code:
    #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.

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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.
    Last edited by nspils; 04-25-2007 at 09:23 PM.

Similar Threads

  1. Shortest Path Algorithm
    By EHump20 in forum C++
    Replies: 4
    Last Post: 03-15-2007, 04:17 PM
  2. The main for Floyd's Algorithm Code
    By comp_student in forum C++
    Replies: 0
    Last Post: 01-15-2007, 05:50 PM
  3. How to add third party algorithm in sql server 2000
    By shipra pandey in forum Database
    Replies: 0
    Last Post: 02-18-2006, 01:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center