need 28 Newbie Poster

Hello,

The program finds the shortest path between the user inputted nodes. The nodes are integer. Now I need to modify my code to find the path between nodes which are string.
Path between A and B instead of 1 and 2. Please help me to convert my code.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct node {
int info;
node *next;
};

class Queue 
{
	public:
	Queue();
	~Queue();
	bool isEmpty();
	void add(int);
	int get();
	private:
	node *first, *last;
	};

class Graph {
	public:
	Graph(int size = 2);
	~Graph();
	bool isConnected(int, int);
	// adds the (x, y) pair to the edge set
	void addEdge(int x, int y);
	// performs a Breadth First Search starting with node x
	void BFS(int x);
	// searches for the minimum length path
	// between the start and target vertices
	void minPath(int start, int target);
	private :
	int n;
	int **A;
	};
Queue::Queue() 
{
	first = new node;
	first->next = NULL;
	last = first;
}
Queue::~Queue() 
{
	delete first;
}

bool Queue::isEmpty() {
return (first->next == NULL);
}

void Queue::add(int x) 
{
	node *aux = new node;
	aux->info = x;
	aux->next = NULL;
	last->next = aux;
	last = aux;
}

int Queue::get() 
{
	node *aux = first->next;
	int value = aux->info;
	first->next = aux->next;
	if (last == aux) last = first;
	delete aux;
	return value;
}

Graph::Graph(int size) 
{
	int i, j;
	if (size < 2) n = 2;
	else n = size;
	A = new int*[n];
	for (i = 0; i < n; ++i)
	A[i] = new int[n];
	for (i = 0; i < n; ++i)
	for (j = 0; j < n; ++j)
	A[i][j] = 0;
}
Graph::~Graph() {
	for (int i = 0; i < n; ++i)
	delete [] A[i];
	delete [] A;
}
bool Graph::isConnected(int x, int y) 
{
return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) 
{
	A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x) 
{
	Queue Q;
	bool *visited = new bool[n+1];
	int i;
	for (i = 1; i <= n; ++i)
	visited[i] = false;
	Q.add(x);
	visited[x] = true;
	//cout << "Breadth First Search starting from vertex ";
	//cout << x << " : " << endl;
while (!Q.isEmpty()) 
{
	int k = Q.get();
	cout << k << " ";
	for (i = 1; i <= n; ++i)
	if (isConnected(k, i) && !visited[i]) 
	{
		Q.add(i);
		visited[i] = true;
	}
}
	cout << endl;
	delete [] visited;
}
void Graph::minPath(int start, int target) 
{
	Queue Q;
	int i, p, q;
	bool found;
	struct aux { int current, prev; };
	aux *X = new aux[n+1];
	int *Y = new int[n+1];
	bool *visited = new bool[n+1];
	for (i = 1; i <= n; ++i)
	visited[i] = false;
	Q.add(start);
	visited[start] = true;
	found = false;
	p = q = 0;
	X[0].current = start;
	X[0].prev = 0;
	while (!Q.isEmpty() && !found) {
	int k = Q.get();
	for (i = 1; i <= n && !found; ++i)
	if (isConnected(k, i) && !visited[i]) {
	Q.add(i);
	++q;
	X[q].current = i;
	X[q].prev = p;
	visited[i] = true;
	if (i == target) found = true;
}
++p;
}
	cout << "The minimum length path from " << start;
	cout << " to " << target << " is : " << endl;
	p = 0;
	while (q) 
	{
		Y[p] = X[q].current;
		q = X[q].prev;
		++p;
	}
Y[p] = X[0].current;
for (q = 0; q <= p/2; ++q) {
int temp = Y[q];
Y[q] = Y[p-q];
Y[p-q] = temp;
}
for (q = 0; q <= p; ++q)
cout << Y[q] << " ";
cout << endl;
cout << "Length = " << q-1 << endl;
delete [] visited;
delete [] X;
delete [] Y;
}

void asgn() {
Graph f(11);
f.addEdge(1, 8); f.addEdge(1, 4); f.addEdge(1, 10);
f.addEdge(10, 4); f.addEdge(10, 11); f.addEdge(10, 5);
f.addEdge(6, 8); f.addEdge(6, 4); f.addEdge(6, 2);
f.addEdge(11, 2); f.addEdge(2, 9); f.addEdge(7, 9);
f.addEdge(7, 11); f.addEdge(3, 5); f.addEdge(11, 9);
f.addEdge(5, 11);
int start, target;
cout<<"Please enter starting point (1-11) :\n";
cin>>start;
cout<<"Please enter target point (1-11) :\n";
cin>>target;
f.minPath(start, target);
}
void main() {
	
cout << endl;
asgn();
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.