Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dijkstra's Algorithm
/* Dijkstra's Algorithm */
#include "stdlib.h"
#include <iostream>
#include "time.h"
#define MAX_PATHS 20
#define RANDOM_MAX_PATHS 2
#define MAX_WEIGHT 10
#define MAX_VERTICES 6
#define MAX_INT 1000000
#define MIN_VERTICES 4
using namespace std;
int totalCost(int v, struct Cost *minCosts);
void makeMap(int *numberOfVertices, struct Vertex *map);
void printMap(int numberOfVertices, struct Vertex *map);
void makeDefaultMap(int *numberOfVertices, struct Vertex *map);
void printMinCosts(int numberOfVertices, struct Cost *minCosts);
void printShortestPathTree(int numberOfVertices, struct Cost *minCosts);
void dijkstra(int numberOfVertices, struct Vertex *map, struct Cost *minCosts);
struct Path
{
char end;
int weight;
};
struct Vertex
{
char name;
struct Path paths[MAX_PATHS];
int numberOfPaths, nextNullPath;
};
struct Cost
{
int cost, previous;
};
int main(void)
{
int numberOfVertices;
struct Cost minCosts[MAX_VERTICES] = {0};
struct Vertex map[MAX_VERTICES] = {0};
for(int a = 0; a < MAX_VERTICES; a++)
{
minCosts[a].previous = -1;
minCosts[a].cost = MAX_INT;
}
minCosts[0].cost = 0;
cout << "------------------------------ DIJKSTRA ------------------------------\n\n";
makeDefaultMap(&numberOfVertices, map);
printMap(numberOfVertices, map);
dijkstra(numberOfVertices, map, minCosts);
printMinCosts(numberOfVertices, minCosts);
printShortestPathTree(numberOfVertices, minCosts);
system("pause");
return 0;
}
int totalCost(int v, struct Cost *minCosts)
{
int result = (minCosts + v)->cost;
for(v = (minCosts + v)->previous; v >= 0 && (minCosts + v)->previous != -1; v = (minCosts + v)->previous)
result += (minCosts + v)->cost;
return result;
}
void printMap(int numberOfVertices, struct Vertex *map)
{
cout << "------------ MAP ------------\n\nNumber of vertices: " << numberOfVertices << "\n\n";
for(int z = 0; z < numberOfVertices; z++)
{
cout << "\n------ Vertex [" << (map + z)->name << "],\nNumber of paths: " << (map + z)->numberOfPaths << "\n";
for(int u = 0; u < (map + z)->numberOfPaths; u++)
{
cout << "\n---Path [" << u << "]\nEnd: " << (map + z)->paths[u].end << "\nWeight: " << (map + z)->paths[u].weight << '\n';
}
cout << "\n\n\n";
}
}
void printMinCosts(int numberOfVertices, struct Cost *minCosts)
{
cout << "------------ minCosts ------------\n\n ------------------\n |Costs |Previous |";
for(int g = 0; g < numberOfVertices; g++)
cout << "\n" << (char)(g + 'A') << "|" << (minCosts + g)->cost << " |" << (minCosts + g)->previous;
cout << endl << endl;
}
void printShortestPathTree(int numberOfVertices, struct Cost *minCosts)
{
cout << "------------ Shortest Path Tree ------------\n\Ending vertex: A\n\n";
for(int g = 1; g < numberOfVertices; g++)
{
cout << "\n---- Staring from: " << (char)(g + 'A') << "\n\n";
for(int a = g; (minCosts + a)->previous != -1; a = (minCosts + a)->previous)
{
cout << " " << (minCosts + a)->cost <<"\n" << (char)(a + 'A') << " - " << (char)((minCosts + a)->previous + 'A') << "\n";
}
}
}
void dijkstra(int numberOfVertices, struct Vertex *map, struct Cost *minCosts)
{
int possibleVertex;
int x;
for(int i = 0; i < numberOfVertices; i++)
{
for(int d = 0; d < (map + i)->numberOfPaths; d++)
{
possibleVertex = ((map + i)->paths[d].end) - 'A';
if(possibleVertex != 0)
{
x = (map + i)->paths[d].weight;
x = totalCost(i, minCosts);
x = totalCost(possibleVertex, minCosts);
if((map + i)->paths[d].weight + totalCost(i, minCosts) < totalCost(possibleVertex, minCosts))
{
(minCosts + possibleVertex)->cost = (map + i)->paths[d].weight;
(minCosts + possibleVertex)->previous = i;
}
}
}
}
}
void makeMap(int *numberOfVertices, struct Vertex *map)
{
srand((unsigned) time(NULL));
/* Set *numberOfVertices to a random number in between MAX_VERTICES and MIN_VERTICES. */
*numberOfVertices = (rand() % ((MAX_VERTICES + 1) - MIN_VERTICES)) + MIN_VERTICES;
for(int i = 0; i < *numberOfVertices; i++)
(map + i)->name = i + 'A';
for(int c = 0; c < *numberOfVertices; c++)
{
if(c != ((*numberOfVertices) - 1) && (map + c)->numberOfPaths < MAX_PATHS && (map + c+1)->numberOfPaths < MAX_PATHS)
{
int randomWeight = rand() % MAX_WEIGHT;
(map + c)->paths[(map + c)->nextNullPath].end = c + 'A' + 1;
(map + c)->paths[(map + c)->nextNullPath].weight = randomWeight;
(map + c)->nextNullPath++;
(map + c)->numberOfPaths++;
(map + c+1)->paths[(map + c+1)->nextNullPath].end = c + 'A';
(map + c+1)->paths[(map + c+1)->nextNullPath].weight = randomWeight;
(map + c+1)->nextNullPath++;
(map + c+1)->numberOfPaths++;
}
(map + c)->numberOfPaths += rand() % RANDOM_MAX_PATHS;
for(int e = (map + c)->nextNullPath; e < MAX_PATHS && e < (map + c)->numberOfPaths; e++)
{
int randomVertex = rand() % *numberOfVertices;
for(; (map + randomVertex)->numberOfPaths >= MAX_PATHS || randomVertex == c;)
randomVertex = rand() % *numberOfVertices;
int randomWeight = rand() % MAX_WEIGHT;
(map + c)->paths[(map + c)->nextNullPath].end = randomVertex + 'A';
(map + c)->paths[(map + c)->nextNullPath].weight = randomWeight;
(map + c)->nextNullPath++;
(map + randomVertex)->paths[(map + randomVertex)->nextNullPath].end = c + 'A';
(map + randomVertex)->paths[(map + randomVertex)->nextNullPath].weight = randomWeight;
(map + randomVertex)->nextNullPath++;
(map + randomVertex)->numberOfPaths++;
}
}
}
void makeDefaultMap(int *numberOfVertices, struct Vertex *map)
{
*numberOfVertices = 6;
for(int i = 0; i < *numberOfVertices; i++)
(map + i)->name = i + 'A';
(map + 0)->paths[(map + 0)->nextNullPath].end = 'B';
(map + 0)->paths[(map + 0)->nextNullPath].weight = 5;
(map + 0)->nextNullPath++;
(map + 0)->numberOfPaths++;
(map + 1)->paths[(map + 1)->nextNullPath].end = 'A';
(map + 1)->paths[(map + 1)->nextNullPath].weight = 5;
(map + 1)->nextNullPath++;
(map + 1)->numberOfPaths++;
(map + 0)->paths[(map + 0)->nextNullPath].end = 'C';
(map + 0)->paths[(map + 0)->nextNullPath].weight = 3;
(map + 0)->nextNullPath++;
(map + 0)->numberOfPaths++;
(map + 2)->paths[(map + 2)->nextNullPath].end = 'A';
(map + 2)->paths[(map + 2)->nextNullPath].weight = 3;
(map + 2)->nextNullPath++;
(map + 2)->numberOfPaths++;
(map + 0)->paths[(map + 0)->nextNullPath].end = 'F';
(map + 0)->paths[(map + 0)->nextNullPath].weight = 6;
(map + 0)->nextNullPath++;
(map + 0)->numberOfPaths++;
(map + 5)->paths[(map + 5)->nextNullPath].end = 'A';
(map + 5)->paths[(map + 5)->nextNullPath].weight = 6;
(map + 5)->nextNullPath++;
(map + 5)->numberOfPaths++;
(map + 1)->paths[(map + 1)->nextNullPath].end = 'C';
(map + 1)->paths[(map + 1)->nextNullPath].weight = 1;
(map + 1)->nextNullPath++;
(map + 1)->numberOfPaths++;
(map + 2)->paths[(map + 2)->nextNullPath].end = 'B';
(map + 2)->paths[(map + 2)->nextNullPath].weight = 1;
(map + 2)->nextNullPath++;
(map + 2)->numberOfPaths++;
(map + 2)->paths[(map + 2)->nextNullPath].end = 'D';
(map + 2)->paths[(map + 2)->nextNullPath].weight = 9;
(map + 2)->nextNullPath++;
(map + 2)->numberOfPaths++;
(map + 3)->paths[(map + 3)->nextNullPath].end = 'C';
(map + 3)->paths[(map + 3)->nextNullPath].weight = 9;
(map + 3)->nextNullPath++;
(map + 3)->numberOfPaths++;
(map + 2)->paths[(map + 2)->nextNullPath].end = 'D';
(map + 2)->paths[(map + 2)->nextNullPath].weight = 4;
(map + 2)->nextNullPath++;
(map + 2)->numberOfPaths++;
(map + 3)->paths[(map + 3)->nextNullPath].end = 'C';
(map + 3)->paths[(map + 3)->nextNullPath].weight = 4;
(map + 3)->nextNullPath++;
(map + 3)->numberOfPaths++;
(map + 3)->paths[(map + 3)->nextNullPath].end = 'E';
(map + 3)->paths[(map + 3)->nextNullPath].weight = 5;
(map + 3)->nextNullPath++;
(map + 3)->numberOfPaths++;
(map + 4)->paths[(map + 4)->nextNullPath].end = 'D';
(map + 4)->paths[(map + 4)->nextNullPath].weight = 5;
(map + 4)->nextNullPath++;
(map + 4)->numberOfPaths++;
(map + 3)->paths[(map + 3)->nextNullPath].end = 'F';
(map + 3)->paths[(map + 3)->nextNullPath].weight = 8;
(map + 3)->nextNullPath++;
(map + 3)->numberOfPaths++;
(map + 5)->paths[(map + 5)->nextNullPath].end = 'D';
(map + 5)->paths[(map + 5)->nextNullPath].weight = 8;
(map + 5)->nextNullPath++;
(map + 5)->numberOfPaths++;
(map + 4)->paths[(map + 4)->nextNullPath].end = 'F';
(map + 4)->paths[(map + 4)->nextNullPath].weight = 2;
(map + 4)->nextNullPath++;
(map + 4)->numberOfPaths++;
(map + 5)->paths[(map + 5)->nextNullPath].end = 'E';
(map + 5)->paths[(map + 5)->nextNullPath].weight = 2;
(map + 5)->nextNullPath++;
(map + 5)->numberOfPaths++;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment