Name: Title:

 Name:
ONLINE COMPILERS
LIBRARY
MANUAL PAGES & DOCS
CONTACT

User Submitted Source Code!

Description:
sas
Language: C/C++
Code:
//============================================================================
// Name        : djikstra.cpp
// Author      : Arun Suresh
// Version     :
// Description :
//============================================================================

#include <iostream>
using namespace std;

#define INFINITY 9999

using namespace std;

class Dijkstra{
private:
int predecessor,distance;
bool mark; //keep track of visited node
int source;
int numOfVertices;
public:
/*
* Function read() reads No of vertices, Adjacency Matrix and source
* Matrix from the user. The number of vertices must be greather than
* zero, all members of Adjacency Matrix must be postive as distances
* are always positive. The source vertex must also be positive from 0
* to noOfVertices - 1

*/

/*
* Function initialize initializes all the data members at the begining of
* the execution. The distance between source to source is zero and all other
* distances between source and vertices are infinity. The mark is initialized
* to false and predecessor is initialized to -1
*/

void initialize();

/*
* Function getClosestUnmarkedNode returns the node which is nearest from the
* Predecessor marked node. If the node is already marked as visited, then it search
* for another node.
*/

int getClosestUnmarkedNode();
/*
* Function calculateDistance calculates the minimum distances from the source node to
* Other node.
*/

void calculateDistance();
/*
* Function output prints the results
*/

void output();
void printPath(int);
};

cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;

for(int i=0;i<numOfVertices;i++) {
//cout<<"Enter the (+ve)weights for the row "<<i<<endl;
for(int j=0;j<numOfVertices;j++) {
adjMatrix[i][j]=rand() % 999 + 1;
cout<<"Weights should be +ve. Enter the weight again\n";
adjMatrix[i][j]=rand() % 999 + 1;
}
}
}
cout<<"The number of vertices are"<<numOfVertices;
cout<<"Enter the source vertex\n";
cin>>source;
while((source<0) && (source>numOfVertices-1)) {
cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl;
cout<<"Enter the source vertex again\n";
cin>>source;
}
}

void Dijkstra::initialize(){
for(int i=0;i<numOfVertices;i++) {
mark[i] = false;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source]= 0;
}

int Dijkstra::getClosestUnmarkedNode(){
int minDistance = INFINITY;
int closestUnmarkedNode;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && ( minDistance >= distance[i])) {
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}

void Dijkstra::calculateDistance(){
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numOfVertices) {
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = true;
for(int i=0;i<numOfVertices;i++) {
if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) {
if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}

void Dijkstra::printPath(int node){
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from Ò<<source<<Óto "<<(char)(node + 97)<<endl;
else {
printPath(predecessor[node]);
cout<<(char) (node + 97)<<"..";
}
}

void Dijkstra::output(){
for(int i=0;i<numOfVertices;i++) {
if(i == source)
cout<<(char)(source + 97)<<".."<<source;
else
printPath(i);
cout<<"->"<<distance[i]<<endl;
}
}

int main(){
Dijkstra G;