Last active
October 14, 2019 01:21
-
-
Save tvandoren/7e03f2774e836253b00967b9542ec51a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <vector> | |
| // starting node (can be anything from 0 to 9) | |
| int START_NODE = 0; | |
| // since int cannot represent infinity, a value high enough above anything we should encounter will be used | |
| int HIGH_VAL = 999; | |
| // size of adjacency matrix | |
| int MATRIX_SIZE = 10; | |
| int main(void) { | |
| /* Since the graph from the test was too simple, this program will run through | |
| Dijkstra's Algorithm for a graph with ten nodes given by the adjacency matrix | |
| given below. */ | |
| // initialize adjacency matrix (dimensions should be the same as MATRIX_SIZE | |
| bool a_matrix[10][10] = | |
| { | |
| {false, true, true, false, false, false, false, false, true, false}, | |
| {false, false, true, false, false, false, false, false, false, false}, | |
| {false, false, false, true, false, false, false, false, true, false}, | |
| {false, false, false, false, true, false, false, false, false, false}, | |
| {true, false, false, false, false, true, false, true, false, true}, | |
| {false, false, false, false, false, false, false, false, false, false,}, | |
| {false, false, false, false, false, false, false, false, false, true}, | |
| {false, false, false, false, false, false, true, false, false, false}, | |
| {false, false, false, false, true, false, false, false, false, false}, | |
| {false, false, false, false, false, true, false, false, false, false}}; | |
| // initialize counter variables | |
| int i, j; | |
| // print matrix to terminal | |
| std::cout << " Adjacency matrix: " << std::endl; | |
| std::cout << " 0 1 2 3 4 5 6 7 8 9" << std::endl; | |
| std::cout << " - - - - - - - - - -"<< std::endl; | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| std::cout << i << " - "; | |
| for(j = 0; j < MATRIX_SIZE; j++) { | |
| if(a_matrix[i][j]) { | |
| std::cout << "1 "; | |
| } else { | |
| std::cout << "0 "; | |
| } | |
| } | |
| std::cout << std::endl; | |
| } | |
| std::cout << std::endl; | |
| // array to store distance values | |
| int distance[MATRIX_SIZE]; | |
| // array to keep track of visited and unvisited nodes | |
| bool visited[MATRIX_SIZE]; | |
| // array to keep track of the discovering node for each node | |
| int found_by[MATRIX_SIZE]; | |
| // initialize all distances to a high number to indicate infinity (since infinity can't actually be represented as an int) | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| distance[i] = HIGH_VAL; | |
| } | |
| // however, distance to start node from start node is 0 | |
| distance[START_NODE] = 0; | |
| // all nodes are originally unvisited | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| visited[i] = false; | |
| } | |
| // all nodes are originally not discovered (indicated by HIGH_VAL) | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| found_by[i] = HIGH_VAL; | |
| } | |
| // flag: indicates if all nodes have been visited | |
| bool all_visited = false; | |
| // node being considered | |
| int current_node = START_NODE; | |
| while(!all_visited) { | |
| // loop through adjacency matrix for current node | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| // if node is adjacent to current node | |
| if(a_matrix[current_node][i] && !visited[i]) { | |
| // update found by if not already found | |
| if(found_by[i] == HIGH_VAL) { | |
| found_by[i] = current_node; | |
| } | |
| // if distance to node is less than recorded, update distance | |
| if(distance[current_node] + 1 < distance[i]) { | |
| distance[i] = distance[current_node] + 1; | |
| } | |
| } | |
| } | |
| // current node is now visited | |
| visited[current_node] = true; | |
| // find shortest distance unvisited node | |
| int closest_distance_node = HIGH_VAL; // set high start | |
| for(i = 0; i < MATRIX_SIZE; i++) { | |
| // destination node should not have been visited yet | |
| if(!visited[i]) { | |
| if(distance[i] < closest_distance_node) { | |
| closest_distance_node = i; | |
| } | |
| } | |
| } | |
| // set shortest distance node as current | |
| current_node = closest_distance_node; | |
| // if closest distance node is still HIGH_VAL, then all nodes have been visited and loop should exit | |
| if(closest_distance_node == HIGH_VAL) { | |
| all_visited = true; | |
| } | |
| } | |
| // get destination node from the user | |
| int destination_node, path_node; | |
| do { | |
| std::cout << "Enter destination node (between 0 and 9): "; | |
| std::cin >> destination_node; | |
| } while(destination_node < 0 || destination_node > 9); | |
| // find path from start node to destination node | |
| path_node = destination_node; | |
| std::vector <int> path; | |
| path.push_back(path_node); | |
| while(path_node != 0) { // find path backwards from current node | |
| path.push_back(found_by[path_node]); | |
| path_node = found_by[path_node]; | |
| } | |
| // print distance and path to specified node | |
| std::cout << "Distance to node from node 0: " << distance[destination_node] << std::endl; | |
| std::cout << "Path (nodes): "; | |
| while(path.size() > 0) { | |
| std::cout << path.back(); | |
| if(path.size() > 1) { | |
| std::cout << "->"; | |
| } | |
| path.pop_back(); | |
| } | |
| std::cout << std::endl; | |
| return(0); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment