Skip to content
{{ message }}

Instantly share code, notes, and snippets.

Danalexanderc/Dijkstra.cpp

Created Aug 28, 2017
Dijkstra's Algorithm
 /* Dijkstra's Algorithm */ #include "stdlib.h" #include #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++; }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.