A graph is a set of points (called vertices, singular vertex) with lines connecting some or all of them. The lines are called edges.
In a directed graph the edges each have an arrow at one end. You can think of this as the allowed direction of movement from one vertex to another. In this case the vertex at the end of the arrow is the target vertex and the vertex at the tail is the source vertex.
In a weighted directed graph the edges also have weights.
Two examples of weighted directed graphs:
| vertex | A node or point in a graph. A vertex can be connected to another vertex or vertices, but it doesn't have to be. |
| edge | A line connecting two vertices. A vertex may be connected by edges to many vertices. A vertex may have many edges connecting it to another vertex. |
| weight | A number attached to an edge. |
| loop | An edge that loops around and connects a vertex to itself. |
| multiple edge | A number of edges that each connect two vertices. |
| path | A way of moving from vertex to edge to vertex to get from a start vertex to an end vertex. |
| traversal | A method of visiting every accessible vertex from a given start vertex. |
| shortest path | A path that moves from a start vertex to an end vertex in a way to minimize the total weight along the edges. |
Two ways:
The following algorithm to find the paths with the smallest total weight to all vertices from a given start vertex is due to the famous computer scientist Edsgar Dykstra.
Given: A weighted, directed graph and a starting vertex.
The result: The least total weights from the starting vertex to every vertex that can be reached from the starting vertex.
Let A be the set of allowed vertices. Initialize this to empty.
Let D be an array with a slot for each vertex in the graph, such that each cell contains the total weight so far.
Let Prev be an array with a slot for each vertex in the graph.
Initialize the total weight in each cell of D to infinity.
The algorithm is:
D[vertex] and
D[next] + Weight of the edge from next to vertex.
Also, the path that gives this least total weight can be printed with:
The classes here represent a weighted, directed graph.
There are four classes in the design:
| The edgeMatrixEntry class | Represents the data in a cell of the adjacency matrix. This data is a true/false flag to tell if there is an edge between two vertices and the weight of an edge. |
| The edgeMatrix class | This is the adjacency matrix. |
| The shortDist class | This class is the mechanism for finding the shortest paths from a given start vertex. |
| The graph class | Represents the graph. |
#include <iostream>
#include <string>
using namespace std;
const int MAX = 20;
//A class to represent the data in a cell of the weighted edge matrix.
class edgeMatrixEntry
{
public:
edgeMatrixEntry () {isactive = false; wt = 0;}
void set (bool flag, int val){isactive = flag; wt = val;}
bool isActive () {return isactive;}
void activate () {isactive = true;}
void deActivate () {isactive = false;}
void setWt (int val) {wt = val;}
int getWt () {return wt;}
edgeMatrixEntry& operator= (edgeMatrixEntry& it)
{isactive = it.isactive; wt = it.wt; return *this;}
private:
bool isactive;
int wt;
};
//A class to represent the adjacency matrix with edge weight information
// in each cell.
class edgeMatrix
{
public:
edgeMatrix ();
void removeEdge (int a, int b); //Removes the edge from a to b
void setEdge (int a, int b); //Creates an edge from a to b
void setEdge (int a, int b, int w); //Creates an edge from a to b with
// weight w
void deleteRow (int); //Deletes a row of the matrix
void deleteCol (int); //Deletes a column of the matrix
bool isEdge (int a, int b); //True, if there is an edge from a
// to b
int getEdgeWt (int a, int b); //Gets the weight of the edge from
// a to b
private:
edgeMatrixEntry matrix [MAX][MAX];
};
//A class to implement Dykstra's shortest path algorithm
class shortDist
{
public:
shortDist (edgeMatrix*, int); //Pass the edge matrix and the number of
// vertices.
void getShortDistances (int start, int distances[], int vertexSequence[]);
private:
edgeMatrix* edges;
int distance [MAX]; //array of shortest distances from the start
int allowed [MAX]; //array of allowed vertices
int pred [MAX]; //aray of predecessor vertices
int allowedCnt;
int size;
bool isAllowed (int v);
void reviseDistances (int v);
int nextAllowed (int v);
void addToAllowedSet (int v);
};
class graph
{
friend ostream& operator<< (ostream&, graph&);
public:
graph ();
void addVertex (char*); //Adds a new vertex to
// the graph
void addEdge (char* s, char* t); //Adds a new edge from vertex
// s to vertex t.
void addEdge (char* s, char* t, int w); //Adds a new edge from
// vertex s to vertex t
// with weight w.
void deleteVertex (char* v); //Deletes vertex v
void deleteEdge (char* s, char* t); //Deletes the edge from vertex
// s to vertex t.
//getShortestDists gets the shortest total weight dist between vertex
// start and vertex finish. The sequence of vertices in the path is
// produced in the array vertexSequence. The number of such
// vertices is produced in cnt.
void getShortestDists (char* start,
char* finish,
string vertexSequence [],
int& dist,
int& cnt);
string getVertex (int n); //Returns the nth vertex.
string operator[] (int n); //Also returns the nth vertex.
private:
string vertex [MAX]; //List of vertex labels
edgeMatrix edges; //The adjacency matrix
int size; //The number of vertices
int findVertex (string& it); //Converts vertex label into
// vertex number
void deleteFromVertexList (int n); //Deletes the nth vertex
};