#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
const int INFINITY = 9999;
const int UNDEFINED = -1;
const int NODES = 8;
using namespace std;
typedef enum Node {A,B,C,D,E,F,G,H} Node;
Node findVertexInQWithSmallestDist(const Node Q[], const int dist[])
{
int i;
Node nodeWithSmallestDist;
for (i = 0; i < NODES; i++) // Find any node to set as the node having the smallest
if (Q[i] != -1) // distance from the source. I set the first node.
{
nodeWithSmallestDist = i;
break;
}
for (i = 0; i < NODES; i++) // find the actual node with the smallest
if (Q[i] != -1) // distance from the source
if (dist[i] < dist[nodeWithSmallestDist])
nodeWithSmallestDist = i;
return nodeWithSmallestDist;
}
void removeNodeFromQ(Node Q[], Node u)
{
Q[u] = -1; // marks the node as removed
}
int distanceBetweenNodes(const int graph[][NODES], Node u, Node v)
{
return graph[u][v];
}
void printShortestPath(const Node prev[], Node dest, int cost)
{
Node path[NODES];
Node currentNode;
int i = 0;
int j;
path[i++] = dest;
for (currentNode = dest; prev[currentNode]+'A' != '@'; i++) // special marker to indicate the starting path
{
path[i] = prev[currentNode];
currentNode = prev[currentNode];
}
cout << "Cost: " << cost << endl;
for (j = i-1; j >= 0; j--)
cout << "Path: " << path[j]+'A';
}
void findShortestPath(const int graph[][NODES], Node src, Node dest)
{
int v;
int alt;
int dist[NODES] = {INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY}; // dist[v] = infinity
Node prev[NODES] = {UNDEFINED,UNDEFINED,UNDEFINED,UNDEFINED,UNDEFINED,UNDEFINED,UNDEFINED,UNDEFINED}; // prev[v] = undefined
Node Q[NODES] = {A,B,C,D,E,F,G,H}; // Q = set of all nodes in the graph
Node u;
int numberOfNodesLeft = NODES;
dist[src] = 0; // dist[source] = 0
while (numberOfNodesLeft > 0) // while Q is not empty
{
u = findVertexInQWithSmallestDist(Q,dist);
if (u == INFINITY)
break;
removeNodeFromQ(Q,u); // remove node u from Q
numberOfNodesLeft--;
for (v = 0; v < NODES; v++) // for each POSSIBLE neighbor v of u
if (Q[v] != -1 && graph[u][v] > 0) // if v is still in Q and is a neighbor of u,
{ // it has a weight
alt = dist[u] + distanceBetweenNodes(graph,u,v);
if (alt < dist[v])
{
dist[v] = alt;
prev[v] = u;
}
}
}
printShortestPath(prev,dest,dist[dest]);
}
int main(int argc, char *argv[])
{
ifstream inStream;
int graph[NODES][NODES];
int i;
int j;
char _src;
char _dest;
Node src;
Node dest;
inStream.open("graph.txt");
if(inStream.fail())
{
cout << "Graph has failed to open";
exit(1);
}
for (i = 0; i < NODES; i++)
for (j = 0; j < NODES; j++)
inStream >> graph[i][j];
inStream.close();
cout << "Enter start point: ";
cin >> _src;
cout << endl;
cout << "Enter end point: ";
cin >> _dest;
_src = toupper(_src);
_dest = toupper(_dest);
src = _src - 'A';
dest = _dest - 'A';
findShortestPath(graph,src,dest);
return 0;
}
perator=(const A& base) function to copy, or a B::B(const A& base) function to construct. Otherwise, the compiler will not know how to construct or copy the data for your bInst object.
