Djikstra's algorithm implementation in C++. Given the input file it outputs the shortest path between the 2 given points symbolically in the output text file.

Djikstra.cpp

/*
Alex Marroquin
CSCI 3333
11-21-12

Homework 8: Djikstra's Algorithm with Heap implementation
main.cpp
*/
#include<string>
#include<iostream>
#include<fstream>
#include <iomanip>
#include "Heap.h"
using namespace std;

void cutstring(string &input, int pos)
{
	string dummy = "";

	for(int i = pos; i < input.length(); i++)
	{
		dummy += input[i];
	}
	input = dummy;
}

string concatenate(string &input)
{
	string ls = "";
	if(input == "")
	{
		return "";
	}
	int size = input.length();
	int cnt = 0;
	int i = 0;
	while(isspace(input[cnt]))
	{
		cnt ++;
		if(cnt == size)
			return "";
	}
	if(cnt == size)
	{
		return "";
	}
	while(cnt < size)
	{
		if(isspace(input[cnt]))
			break;
		ls += input[cnt];
		cnt++;
	}
	cutstring(input,cnt);
	return ls;
}


class node
	{
	public:
		double data;
		double weight;
		bool path;
		int count;
		node *next;
		node *pred;
		node(){path = false; next = NULL;pred = NULL;weight = 100000000;count = -1;};
		node(double d, int cnt){path = false;data = d; next = NULL;pred = NULL;weight = 100000000;count = cnt;};
	};
class List
{
public:
	
	node *head;
	List();
	~List();
	bool empty();
	void display();
	void printList();
	void addNeighbor(double,int);
	double getHeadVal();
	int getCount();
};

List::List()
{
	head = NULL;
}

List::~List()
{
	while(!empty())
    {
      node* temp = head;
      head=head->next;
      delete temp;
    }
}

void List::printList()
{
	cout<<"Head Count: "<<head->count<<",  ";
	cout<<"Data: "<<head->data<<",  ";
	cout<<"Weight: "<<head->weight<<endl;
}

bool List::empty()
{
	if(head == NULL)
		return true;
	return false;
}

void List::display()
{
	if(head != NULL)
	{
		node *d = head;
		while(d != NULL)
		{
			cout<<d->data<<" ";
			d = d->next;
		}
		cout<<endl;
	}
}
void List::addNeighbor(double val, int cnt)
{
	if(head == NULL)
	{
	   node *temp = new node(val,cnt);
       head = temp;
	}
	else
	{
		node *dummy = new node(val,cnt);

		node *temp = head;
		while(temp->next != NULL)
			temp = temp->next;
		temp->next = dummy;
	}

}

double List::getHeadVal()
{
	if(head != NULL)
	{
		return head->data;
	}
	return 0;
}
int List::getCount()
{
	if(head != NULL)
	{
		return head->count;
	}
	return 0;
}

void relax(node* &a, node* &b)
{
	if(a->weight + b->data < b->weight)
	{
		b->weight = b->data + a->weight;
		b->pred = a;
	}
}

void Dijkstra(List* &G, Heap <node*>cloud, int end_cnt)
{
	node *dummy, *run;
	int Q = cloud.heapSize();
	int key,sz;
	
	//Loop until no more items are in the heap
	while(!cloud.empty())
	{
		sz = cloud.heapSize();
		dummy = cloud.extractMin();	
		run = dummy->next;
		
		//Go through all the neighbors of the removed item
		while(run != NULL)		
		{
			double old_w = run->weight;
			relax(dummy,run);
			if(run->pred != NULL)
			{
				cout<<"The predecessor: "<<run->pred->data<<endl;
			}

			key = cloud.getIndex(run);
			cloud.decreaseVal(key, run->weight);

			//Find in the adj. list the location of the neighbor (run)
			//and update it's weight
			for(int i = 0; i < Q; i++)
			{
				if(G[i].head->count == run->count)
				{
					G[i].head->weight = run->weight;
					G[i].head->pred = run->pred;
					break;
				}
			}
			
			//Get the neighbor by reference
			node *up = cloud.getItem(run->count);
			
			//Access all neighbors of up by reference and change
			//the weight & predecessor of up in those neighbors to 
			//prevent the copies in the adjacency list from having 
			//different values
			node *check = up->next;
			while(check != NULL)
			{
				node *change = cloud.getItem(check->count);
				while(change != NULL)
				{
					if(up->count == change->count)
					{
						change->weight = up->weight;
						change->pred = up->pred;
					}
					change = change->next;
				}
				check = check->next;
			}

			//Break after reaching the desired node
			if(run->count == end_cnt)
				break;
			run = run->next;
		}
	}
}
int main()
{
	ifstream inFile("grids.txt");
	ofstream outFile("output.txt");
	
	List *graph;
	if(inFile.is_open())
	{
		
		//Reads the start and end position
		string s;
		getline(inFile,s);
		string start = s;
		getline(inFile,s);
		string end = s;
	
		//Converts the data from string to integers
		string f = concatenate(start);
		string g = concatenate(start);
		int start_x = atoi(f.c_str());
		int start_y = atoi(g.c_str());
		
		f = concatenate(end);
		g = concatenate(end);
		int end_x = atoi(f.c_str());
		int end_y = atoi(g.c_str());
		cout<<"Start: "<<start_x<<","<<start_y<<endl;
		cout<<"End: "<<end_x<<","<<end_y<<endl;
		
		//Get amount of items in matrix to store in Adj. List
		getline(inFile,s);
		string dummy = s;
		//Get the # of rows
		int dimension_1 = 0;
		while(dummy != "")
		{
			f = concatenate(dummy);
			dimension_1++; //the # of elements in the first row
		}
		string items = s + " & ";
		
		//Obtain the # of columns
		int dimension_2 = 1;
		while(!inFile.eof())
		{
			getline(inFile,s);
			items += s + " & ";
			dimension_2++; //the # of columns in the matrix
		}
		
		int quantity = dimension_2*dimension_1;
		graph = new List[quantity];
		
		int cnt = 0;
		double x,x_prev, vert;
		while(items != "" && cnt < quantity)
		{
			//Obtain characters from string
			f = concatenate(items);	   
			if(f != "&")
			{
				//Convert string to double
				x = atof(f.c_str());  
				
				//Add the appropriate neighbors to each item
				//in the adjacency list
				graph[cnt].addNeighbor(x,cnt);
				if(cnt != 0 && cnt%dimension_1 != 0)
				{
					graph[cnt-1].addNeighbor(x,cnt);
					graph[cnt].addNeighbor(x_prev,cnt-1);
				}
				if(cnt > dimension_1 - 1)
				{
					vert = graph[cnt-dimension_1].getHeadVal();
					graph[cnt-dimension_1].addNeighbor(x,cnt);
					graph[cnt].addNeighbor(vert,cnt-dimension_1);
				}
				cnt++;
				x_prev = x;
			}
		}
		
		int start_cnt = start_y + dimension_1*(start_x - 1) - 1; //Get the count of the starting point
		int end_cnt = end_y + dimension_1*(end_x - 1) - 1;		//Get the count of the ending point
		graph[start_cnt].head->weight = 0; //Set starting point weight to 0
		cout<<"Start cnt: "<<start_cnt<<"  Val: "<<graph[start_cnt].getHeadVal()<<" Weight: "<<graph[start_cnt].head->weight<<endl;
		cout<<"End cnt: "<<end_cnt<<"  Val: "<<graph[end_cnt].getHeadVal()<<" Weight: "<<graph[end_cnt].head->weight<<endl<<endl;

		//Create a heap in which to store all the vertexes/elements
		Heap <node*> cloud(quantity);
		for(int i = 0; i < quantity; i++)
		{
			cloud.insert(graph[i].head);
		}

		Dijkstra(graph, cloud, end_cnt);

		//For some reason the weight and 
		//predecessor of the start place is 
		//incorrect but it is the only one
		graph[start_cnt].head->weight = 0;
		graph[start_cnt].head->pred = NULL;

		//Mark the path to the end vertex
		node *p = graph[end_cnt].head;
		while(p->pred != NULL)
		{
			p->path = true;
			p = p->pred;
		}

		int track = 0;		//to keep track of the # of items printed per row
		for(int i = 0; i < quantity; i++)
		{
			cout<<"Count: "<<graph[i].head->count;
			cout<<", Data: "<<graph[i].head->data<<", Weight: "<<graph[i].head->weight<<"  ";
			
			//To denote the start vertex
			if(i == start_cnt)
			{
				cout<<"s ";
				outFile<<"s ";
			}
			//To denote the end vertex
			else if(i == end_cnt)
			{
				cout<<"e ";
				outFile<<"e ";
			}
			//To denote the path taken
			else if(graph[i].head->path == true)
			{
				cout<<"@ ";
				outFile<<"@ ";
			}
			else
			{
				outFile<<"* ";
			}
			track++;
			
			//If the # of elements printed is the same as the # of elements
			//originally read from the file a return character is printed
			//to the text file
			if(track == dimension_1)
			{
				outFile<<"\n\n";
				track = 0;
			}
			if(graph[i].head->pred != NULL)
			{
				//For some reason the predecessors are always NULL
				cout<<"Pred val: "<<graph[i].head->pred->data<<endl;
			}
			else
			{
				cout<<endl;
			}
		}

	}
	else
	{
		cout<<"Not here"<<endl;
	}
	
	
	outFile.close();
	inFile.close();
	system("pause");
	return 0;
}

Heap

#ifndef HEAP_AM
#define HEAP_AM
/*
Alex Marroquin
CSCI 3333
11-21-12

Homework 8: Djikstra's Algorithm with Heap implementation
heap.h
*/
#include <iostream>
using namespace std;

template<class THING>
class Heap
{
private:
	//array to hold items
	THING * items;
	int n;

	//return index of parent of i
	int parent(int i)
	{
		return (i-1)/2;
	}

	//return index of left child of i
	int lchild(int i)
	{
		return i*2 + 1;
	}

	//return index of right child of i
	int rchild(int i)
	{
		return i*2 + 2;
	}

	//return index of smaller child
	int minChild(int i)
	{
		if( lchild(i) >= n ) //a leaf!
			return i;
		else if( lchild(i) == (n-1) )
			return lchild(i);
		else if( items[lchild(i)]->weight < items[rchild(i)]->weight )
			return lchild(i);
		else
			return rchild(i);
	}


	//bubble item at index current up tree
	//until there's no more violation
	void bubbleUp(int current)
	{
		if( current == 0 ) //the root! easy!
		{
			//do nothing, done, no violation, base case!
		}
		else if( items[current]->weight >= items[parent(current)]->weight ) //no violation
		{
			//do nothing!, done, go home, base case!
		}
		else
		{
			//step 1: swap current with parent
			swap( items[current], items[parent(current)] );

			//step 2: keep bubbling item up
			bubbleUp( parent(current) );
		}
	}

	void bubbleDown(int current)
	{
		if( lchild(current) >= n  ) //current is a leaf....
		{
			//do nothing! base case!! party down!
		}
		else if( items[current]->weight <= items[minChild(current)]->weight  ) //no violation..
		{
			//done!1 party down! base case
		}
		else
		{
			//step 1: swap with min child
			int mchild = minChild(current);
			swap( items[current], items[mchild] );

			//step 2: continue bubbling down
			bubbleDown(mchild);
		}
	}

public:
	Heap(int cap)
	{
		items = new THING[cap];
		n=0;
	}

	//return true if heap is empty
	bool empty()
	{
		if( n==0 )
			return true;
		else
			return false;
	}
	
	//To check if item is in heap
	int getIndex(THING a)
	{
		
		for(int i = 0; i < n; i++)
		{
			if(items[i]->data == a->data && items[i]->count == a->count)
			{
				return i;
			}
		}
		return -1;
	}

	
	//To change the weight of the particular item in the heap
	void decreaseVal(int index, double val)
	{
		if(index == -1)		//if item is not in heap
			return;
		if(items[index]->weight == val)
			return;
		double old_w = items[index]->weight;
		items[index]->weight = val;
		if(old_w == 100000000)
		{
			bubbleUp(index);
		}
		else
		{
			bubbleDown(index);
		}
	}

	double getVal(int index)
	{
		return items[index]->data;
	}

	double getWeight(int index)
	{
		return items[index]->weight;
	}

	void printHeap()
	{
		cout<<endl<<"Printing Heap . . ."<<endl;
		for(int i = 0; i < n; i++)
		{
			cout<<"Index: "<<i;
			cout<<",  Count: "<<items[i]->count;
			cout<<",  Val: "<<items[i]->data;
			cout<<",  Weight: "<<items[i]->weight<<endl;
			
		}
		cout<<"Heap Printed."<<endl<<endl;
	}

	//add item x to heap
	void insert(THING &x)
	{
		//step 1:  add x to end of array
		items[n] = x;
		n++;

		//step 2: bubble up!
		bubbleUp(n-1);
	}

	//Used to access by reference items in the heap in case
	//they need to be fixed
	THING &getItem(int cnt)
	{
		for(int i = 0; i < n; i++)
		{
			if(items[i]->count == cnt)
			{
				return items[i];
			}
		}
	}
	
	//remove and return smallest item in heap
	THING extractMin()
	{
		//step 1: store root item in output box
		THING output = items[0];

		//step 2: put last item at root
		items[0] = items[n-1];
		n--;

		//step 3: bubble down!
		bubbleDown(0);

		return output;
	}

	void heapSort(THING * A, int n)
	{
		//step 1:
		for(int i=0; i<n; i++)
			insert_cnt(A[i]);

		//step 2:
		for(int i=0; i<n; i++)
			A[i] = extractMin_cnt();
	}

	int heapSize()
	{
		return n;
	}

};

#endif

input.txt

2 3
6 6
1.35        3.12        3.32        4.13        1.50        1.02        3.73
3.65        9.74        3.74        1.10        1.30        6.02        3.75
1.45        8.49        2.62        4.15        1.20        3.34        3.13
6.30        5.10        7.32        4.16        6.80        7.02        3.85
1.35        3.10        3.52        4.17        1.30        3.02        3.73
1.33        8.10        6.45        4.17        1.90        2.53        2.71
1.65        1.10        7.14        4.19        1.10        1.32        5.74