Given the map of a country, there could be more than one shortest path between any pair of cities. A transportation hub is a city that is on no less than k shortest paths (the source and the destination NOT included).
Aim
Find for a given pair of cities, the transportation hubs on the way.
What we need to do
The adjacency table is used to construct the graph as a data structure, after reading the data, then Dijkstra’s algorithm is used to find the length of the shortest paths, then the backtracking algorithm is used to find all the shortest paths, and all these paths are stored in an array consisting of a chained list, and then finally traversed to find the transportation hubs as per the requirement.
Why do this
Because the comparative data is scattered, I chose to construct the graph as a data structure using an adjacency table. Because I want to find all the shortest paths, so I need to find the length of the shortest paths first, and then I can find all the shortest paths through the backtracking algorithm, in order to find the transportation hub so I need to traverse the previous paths.
Chapter 2: Algorithm Specification
data structure
vertex structure:
int dist: represents the distance of the node to the start node.
int path: indicates the path of the node, i.e. from the start node to the parent of the current node.
int known: indicates whether the node is known, i.e. whether the shortest path has been calculated.
Edge struct:
int dest: indicates the target node of the edge.
int length: the length of the edge.
struct Edge *next: pointer to other neighboring edges.
PathNode struct:
int vertex: represents the value of the path node.
struct PathNode *next: pointer to the next node.
PathList struct:
PathNode *head: pointer to the first node.
PathList *next: pointer to the next path list.
cnt_onpath Array:
Used to store the number of node visits through the shortest path.
graph array:
Used to store the adjacency table, representing the structure of the graph.
v array:
Used to store information about the node, including the distance from the node to the start node, the path of the node and whether the node is known.
visited array:
Used to record whether a node has been visited.
pathLists array:
Used to store a list of all paths, each path list includes a linked list of the nodes in the path.
These data structures each play different roles in the code for representing the structure of the graph, recording node information, recording paths, and implementing Dijkstra’s algorithm. By using these data structures appropriately, the path problem between nodes in the graph can be solved effectively.
graph TD A(Start) --> B(Input thresholds) B --> C{Loop m times} C --> D(Read edge information) D --> E(Create edge) E --> F(Add edge to graph) F --> G(Create reverse edge) G --> H(Add reverse edge to graph) H --> C C --> I(Read T) I --> J(Initialize ans array) J --> K{Loop T times} K --> L(Initialize cnt_onpath array) L --> M(Read src and dst) M --> N(Initialize visited array) N --> O(Initialize pathLists) O --> P(Call Dijkstra's algorithm) P --> Q(Backtrack paths) Q --> R(Count node visits) R --> S(Update ans array) S --> K K --> T(Print nodes in ans) T --> K T --> U(Print None) U --> K K --> V{Loop T times} V --> W(Print newline) W --> X(End)
Function main(): Declare integer variables n, m, k Read the values of n, m, and k from the input
Loop m times: Declare integer variables len, src, des Read the values of src, des, and len from the input
Create a new edge with the destination des and length len Add the new edge to the list of edges for the source vertex src
Create a new edge with the destination src and length len Add the new edge to the list of edges for the destination vertex des
Declare an integer variable T Read the value of T from the input
Declare a 2D integer array ans of size 505x505 and initialize it to 0
Loop T times: Declare integer variables src, dst Read the values of src and dst from the input
Initialize the counter array cnt_onpath
Declare an integer array visited of size 505 and initialize it to 0
Create a new pathLists object and initialize its head to a path node with destination dst
Call the Dijkstra's algorithm function with parameters n, src, and dst
Backtrack from the goal node and find all the shortest paths
Count the number of visits to nodes on all shortest paths
For each node: If the number of 1s in its binary representation is greater than or equal to k: Set ans[j][i] to 1
Loop T times: Declare an integer variable flg and set it to 0
For each column j in the matrix ans: If the element ans[i][j] is equal to 1: If flg is 0: Print the element Set flg to 1 Otherwise: Print a space followed by the element
If flg is still 0: Print "None"
Print a newline character
Return 0
dijkstra’s algorithm: finding the length of the shortest circuit
graph TD A(Start) --> B(Initialize variables) B --> C(Set source vertex distance to 0) C --> D(Loop until all vertices are processed) D --> E(Find vertex with minimum distance) E --> F(Mark vertex as processed) F --> G(Update distances and paths of adjacent vertices) G --> D D --> H(End) H --> I(Display result)
style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px style G fill:#f9f,stroke:#333,stroke-width:2px style H fill:#f9f,stroke:#333,stroke-width:2px style I fill:#f9f,stroke:#333,stroke-width:2px
Function dijkstra(n, src, dst): // Initialize the distance, path, and known value for all vertices For each vertex v[i] from 0 to 504: v[i].dist = 1000000000 v[i].path = -1 v[i].known = 0
// Set the distance of the source vertex to 0 v[src].dist = 0
// The number of vertices that have been processed cnt = 0
// The current vertex V = 0
// The algorithm continues to run until all vertices have been processed While cnt < n: // Find the vertex with the minimum distance min_dist = 1000000000 min_idx = -1
For each vertex v[i] from 0 to n-1: // If the vertex has not been processed and its distance is less than the minimum distance If not v[i].known and v[i].dist < min_dist: // Update the minimum distance and index min_dist = v[i].dist min_idx = i
// If no more vertices can be found, break the loop If min_idx == -1: Break the loop
// Update the current vertex V = min_idx
// Mark the vertex as processed v[V].known = 1 cnt = cnt + 1
// Update the distances and paths of the adjacent vertices For each edge e in graph[V]: w = e.dest
If not v[w].known and v[w].dist > v[V].dist + e.length: v[w].dist = v[V].dist + e.length v[w].path = V
Return
backtrackPaths :Backtrack to find all shortest paths
graph LR A(Start) --> B(If destination is reached) B --> C(Add new path to list) C --> H(End) B --> D(Iterate through edges) D --> E(Check distance and node visited) E --> F(If distance and visited condition met) F --> G(Add node to current path) G --> D E --> D F --> D D --> B D --> H
style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px style G fill:#f9f,stroke:#333,stroke-width:2px style H fill:#f9f,stroke:#333,stroke-width:2px
Function backtrackPaths(src, dst, visited): // If the destination is reached, add a new path to the list If dst == src: pathLists_tail++ pathLists_tail->head = NULL pathLists_tail->next = NULL flag = 0 Return
// Iterate through the edges of the destination node For each edge e in graph[dst]: prev = e.dest
// If the distance to the destination node is smaller than the previous distance and the node is not visited yet If v[prev].dist == v[dst].dist - e.length and not visited[prev]: // If the path list is empty and the flag is not set If pathLists_tail->head == NULL and not flag: // Copy the path list of the previous node oldlist = pathLists_tail - 1 For each node in oldlist->head until node->vertex == dst: // Add the node to the current path addNodeToPath(node->vertex)
// Add the destination node to the current path addNodeToPath(dst) // If the path list is empty Else if pathLists_tail->head == NULL: // Add the destination node to the current path addNodeToPath(dst)
// Mark the node as visited visited[prev] = 1 // Add the node to the current path addNodeToPath(prev)
// Recursively call the function with the next node as the destination backtrackPaths(src, prev, visited) // Unmark the node as visited visited[prev] = 0
createPathNode：Used to create new nodes
sketch
1 2 3 4 5 6 7 8 9 10 11 12 13 14
graph LR A(Start) --> B(Allocate memory for new PathNode) B --> C(Set vertex value) C --> D(Set next pointer to NULL) D --> E(Return pointer to new PathNode) E --> F(End)
style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px
Pseudocode
1 2 3 4 5 6 7 8 9
Function createPathNode(vertex): // Allocate memory for a new PathNode node = allocate memory for PathNode // Set the vertex value of the new PathNode node->vertex = vertex // Set the next pointer of the new PathNode to NULL node->next = NULL // Return the pointer to the new PathNode Return node
graph LR A(Start) --> B(Create new node with given vertex) B --> C(Check if tail of path list is empty) C --> D(Set head of path list to new node) D --> H(End) C --> E(Set current node pointer) E --> F(Loop through nodes until next pointer is null) F --> G(Set current node to next node) G --> F F --> E E --> I(Set next pointer of current node to new node) I --> H
style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px style G fill:#f9f,stroke:#333,stroke-width:2px style H fill:#f9f,stroke:#333,stroke-width:2px style I fill:#f9f,stroke:#333,stroke-width:2px
Pseudocode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Function addNodeToPath(vertex): // Create a new node with the given vertex newNode = createPathNode(vertex) // If the tail of the path list is empty If (pathLists_tail)->head is NULL: // Set the head of the path list to the new node (pathLists_tail)->head = newNode // Otherwise Else: // Set a pointer to the current node current = (pathLists_tail)->head // Loop through the nodes until the next pointer is null While current->next is not NULL: current = current->next // Set the next pointer of the current node to the new node current->next = newNode
countNodesInPaths:Used to count the nodes passed on the path
graph LR A(Start) --> B(Loop through each path list) B --> C(Check if current list is not the tail) C --> D(Set pointer to the current list) D --> E(Loop through each node in the path list) E --> F(Check if current node exists) F --> G(Check if current node is not the source or destination) G --> H(Increment count for current node) H --> F G --> F F --> E E --> C C --> B B --> I(End)
style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#f9f,stroke:#333,stroke-width:2px style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px style G fill:#f9f,stroke:#333,stroke-width:2px style H fill:#f9f,stroke:#333,stroke-width:2px style I fill:#f9f,stroke:#333,stroke-width:2px
Pseudocode
1 2 3 4 5 6 7 8 9
Function countNodesInPaths(n, src, des): // Loop through each path list For each list in pathLists: // Loop through each node in the path list For each node in list: // If the node is not the source or destination node If node.vertex is not equal to src and node.vertex is not equal to des: // Increment the count for the current node cnt_onpath[node.vertex] += 1
The time complexity of Dijkstra’s algorithm is O(V^2), where V is the number of vertices. In this code, an adjacency table is used to represent the graph and hence the time complexity of Dijkstra’s algorithm is O(V^2).
The process of backtracking paths involves traversing all the shortest paths, so the time complexity depends on the number of shortest paths. In the worst case, all the nodes are on the shortest paths and hence the time complexity of backtracking path is O(V).
The process of counting the number of nodes involves traversing all the nodes on the shortest path and hence the time complexity also depends on the number of shortest paths. In the worst case, all the nodes are on the shortest path and hence the time complexity of counting the number of nodes is O(V).
Therefore, the time complexity of the overall code is O(V^2).
Space complexity analysis:
The space complexity of an adjacency table is O(V + E), where V is the number of vertices and E is the number of edges. In this code, an adjacency table is used to represent the graph, so the space complexity is O(V + E).
Additional vertex structures are used to store node information, and PathNode and PathList structures to store path information. Therefore, the additional space complexity is O(V).
Therefore, the overall space complexity of the code is O(V + E).
Possible further improvements:
Optimized Search Algorithm: The time complexity of Dijkstra’s algorithm is its main bottleneck. Consider using other more efficient algorithms such as A* search (which can achieve O(b^d) when heuristic information is available, where b is the branching factor and d is the average of the heuristic functions, and is usually faster than Dijkstra’s O(V^2)), or use a priority queue (e.g., binary heap) to optimize the path search process.
Use of parallel computation: If the problem can be processed in parallel, e.g., working independently on multiple paths, consider using multithreading or multiprocessing to speed up the search.
Pruning strategies: When backtracking paths, pruning techniques can be used, such as stopping the search as soon as a shorter path is found, to avoid unnecessary computation.
Data structure optimization: If the edges of the graph are sparse and the weights of the edges are evenly distributed, you can consider using adjacency matrix instead of adjacency table, but the space complexity will be higher.
// Initialize the counter array int cnt_onpath[505] = {0};
// Definition of an adjacency table node that treats edges as nodes typedefstructvertex { // Distance of the node from the starting node int dist; // The path of the node int path; // A flag to check if the distance of the node has been calculated int known; } vertex; typedefstructEdge { int dest; // Target vertex int length; // Length of the edge structEdge *next;// Pointer to other neighboring edges } Edge;
// Creates a new edge and connects it to the end of the list //Creates a new edge with a given destination and length Edge *createEdge(int dest, int length) { //Allocates memory for a new edge Edge *edge = (Edge *)malloc(sizeof(Edge)); //Sets the destination of the edge edge->dest = dest; //Sets the length of the edge edge->length = length; //Sets the next edge to NULL edge->next = NULL; //Returns the new edge return edge; } // void dijkstra(int n, int src, int dst) is a function that calculates the shortest path between two nodes in a graph using Dijkstra's algorithm voiddijkstra(int n, int src, int dst); // void cnt(vertex *v, int src, int dst, int n, int k) is a function that counts the number of shortest paths between two nodes in a graph voidcnt(vertex *v, int src, int dst, int n, int k);
// A list of nodes used to store paths // A structure to hold a path from a vertex to the next typedefstructPathNode { // The vertex this pathnode leads to int vertex; // The next pathnode in the path structPathNode *next; } PathNode;
// Used to keep a list of all paths typedefstructPathList { // pointer to the first node in the list PathNode *head; // pointer to the next PathList in the list structPathList *next; } PathList;
// Create a new path node //This function creates a new PathNode with the specified vertex value and returns a pointer to it. PathNode *createPathNode(int vertex) { //Allocate memory for a new PathNode PathNode *node = (PathNode *)malloc(sizeof(PathNode)); //Set the vertex value of the new PathNode node->vertex = vertex; //Set the next pointer of the new PathNode to NULL node->next = NULL; //Return the pointer to the new PathNode return node; } // Array to store path lists PathList pathLists[100]; // Pointer to the head of the path list PathList *pathLists_head = pathLists; // Pointer to the tail of the path list PathList *pathLists_tail = pathLists; int desti; // Function to add a node to the end of the path list voidaddNodeToPath(int vertex) { // Create a new node with the given vertex PathNode *newNode = createPathNode(vertex); // If the tail of the path list is empty if (!(pathLists_tail)->head) { // Set the head of the path list to the new node (pathLists_tail)->head = newNode; } // Otherwise else { // Set a pointer to the current node PathNode *current = (pathLists_tail)->head; // Loop through the nodes until the next pointer is null while (current->next) { current = current->next; } // Set the next pointer of the current node to the new node current->next = newNode; } }
int flag = 1; // Backtrack from a given vertex and find all shortest paths voidbacktrackPaths(int src, int dst, int *visited) { // If the destination is reached, add a new path to the list if (dst == src) { pathLists_tail++; pathLists_tail->head = NULL; pathLists_tail->next = NULL; flag = 0; return; }
// Iterate through the edges of the destination node for (Edge *e = graph[dst]; e != NULL; e = e->next) { int prev = e->dest; // If the distance to the destination node is smaller than the previous distance and the node is not visited yet if (v[prev].dist == v[dst].dist - e->length && !visited[prev]) { // If the path list is empty and the flag is not set if (pathLists_tail->head == NULL && !flag) { // Copy the path list of the previous node PathList *oldlist = pathLists_tail - 1; for (PathNode *node = oldlist->head; node->vertex != dst; node = node->next) { // Add the node to the current path addNodeToPath(node->vertex); } // Add the destination node to the current path addNodeToPath(dst); } // If the path list is empty elseif (pathLists_tail->head == NULL) { // Add the destination node to the current path addNodeToPath(dst); } // Mark the node as visited visited[prev] = 1; // Add the node to the current path addNodeToPath(prev);
// Recursively call the function with the next node as the destination backtrackPaths(src, prev, visited); // Unmark the node as visited visited[prev] = 0; } } } // Count the number of visits to nodes on all shortest paths voidcountNodesInPaths(int n, int src, int des) { // Loop through each path list for (PathList *list = pathLists_head; list != pathLists_tail; list++) { // Loop through each node in the path list for (PathNode *node = list->head; node; node = node->next) { // If the node is not the source or destination node if (node->vertex != des && node->vertex != src) { // Increment the count for the current node cnt_onpath[node->vertex]++; } } } }
// Calling backtrackPaths and countNodesInPaths in the main function
intmain() { int n, m, k; scanf("%d %d %d", &n, &m, &k); // Enter the thresholds for the number of vertices, edges, and transportation hubs respectively for (int i = 0; i < m; i++) { int len; int src, des; // Read the source and destination vertices, and the length of the edge. scanf("%d", &src); scanf("%d", &des); scanf("%d", &len); // Create a new edge with the given source, destination, and length. Edge *edge = createEdge(des, len); // Add the new edge to the existing list of edges for the source vertex. edge->next = graph[src]; graph[src] = edge; // Add this edge to the first one in the adjacency table. // Since this is an undirected graph, we also need to add a reverse edge // So we create a new edge with the source and destination reversed, and add it to the list of edges for the destination vertex. edge = createEdge(src, len); edge->next = graph[des]; graph[des] = edge; } int T; scanf("%d", &T); int ans[505][505] = {0}; // Initialize the answer array for (int j = 0; j < T; j++) { // Initialize the counter array int src, dst; for (int i = 0; i < 505; i++) { cnt_onpath[i] = 0; } scanf("%d %d", &src, &dst); desti = dst; // Used to mark if a node was visited during backtracking int visited[505] = {0};
// Use to keep a list of all shortest paths pathLists_tail = pathLists; pathLists->head = createPathNode(dst); pathLists->next = NULL;
// Backtrack from the goal node and find all the shortest paths backtrackPaths(src, dst, visited); // Count the number of visits to nodes on all shortest paths countNodesInPaths(n, src, dst); // for each node, if the number of 1s in its binary representation is greater than or equal to k, set ans[i][j] = 1 for (int i = 0; i < n; i++) { if (cnt_onpath[i] >= k) { ans[j][i] = 1; } } } // for each test case, print the nodes that ans[i][j] is equal to 1 for (int i = 0; i < T; i++) { // flag is used to check if an element has been printed int flg = 0; // iterate through the columns of the matrix for (int j = 0; j < n; j++) { // if the element exists in the matrix if (ans[i][j]) { // if flag is 0, print the element if (!flg) { printf("%d", j); // set flag to 1 flg = 1; } // otherwise, print the element with a space before it else { printf(" %d", j); } } } // if flag is still 0, that means no element was printed, so print "None" if (!flg) { printf("None"); } // print a newline character printf("\n"); } return0; } voiddijkstra(int n, int src, int dst) { // Implement the dijkstra algorithm // Initialize the distance, path, and known value for all vertices for (int i = 0; i < 505; i++) { v[i].dist = 1000000000; v[i].path = -1; v[i].known = 0; } // Set the distance of the source vertex to 0 v[src].dist = 0; // The number of vertices that have been processed int cnt = 0; // The current vertex int V; // The algorithm continues to run until all vertices have been processed while (cnt < n) { // Find the vertex with the minimum distance int min_dist = 1000000000; int min_idx = -1; for (int i = 0; i < n; i++) { // If the vertex has not been processed and its distance is less than the minimum distance if (!v[i].known && v[i].dist < min_dist) { // Update the minimum distance and index min_dist = v[i].dist; min_idx = i; } } // If no more vertices can be found, break the loop if (min_idx == -1) break; // Update the current vertex V = min_idx; // Mark the vertex as processed v[V].known = 1; cnt++; // Update the distances and paths of the adjacent vertices for (Edge *e = graph[V]; e != NULL; e = e->next) { int w = e->dest; if (!v[w].known && v[w].dist > v[V].dist + e->length) { v[w].dist = v[V].dist + e->length; v[w].path = V; } } } return; }
Declaration
I hereby declare that all the work done in this project titled “Transportation Hub“ is of my independent effort.
