DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
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
{
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. Senior Member
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.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise