The 2ndshortest Path
Date:11.19.2021
Update Log 11.25.2021:
Comptability：
Known issue has been included in README.md
Recommend to compile with clang++，or Visual Studio 2019 CE.
Lab Files has been compiled and reviewed under MacOS 12.0.1，and Windows 10 + CMake 3.19 + Visual Studio Community 2019.Set CMake minimum requirement to 3.14
Performance Improvement：
Using C++ 11 rvalue reference/move semantics to mitigate the copy construction overhead, 5% speed improvement under large case
Using C++11 std::future, std::async for async function calls, with 5% improvement in speed.
1 #define __THREADING__
Chapter 1: Introduction
Given M vertices, indexed from 1 to M, and N edges to represent a Directional Graph.
(In my implementation, both directional and undirectional graph works fine.)
To simplify the problem, the starting point is vertex 1 and the destination is vertex M.
Task: Find Out the Second Shortest Path
 Allow Backtracking: means each vertex can be presented in the path more than once.
 e.g. Path: 1>2>1>3 is valid
 Multiple Shortest Path: if multiple shortest path exists, the second shortest path is the one whose length is longer than those but no longer than any other path.
 e.g. The length of all possible paths are 100,100,105,110. The second shortest path length is 105.
 If two or more second shortest paths exist, any second shortest path would be accepted.
Input Specification:
In the first line specifies the number of vertices M and number of edges N of a digraph.
Then the rest N lines, each line is consisted of a edge, given by:
1  sourceVertex destVertex pathLength 
 Vertex is numbered from 1 to M
 Only positive path length are considered
Constraints:
 $1\le M\le1000$
 $1\le N\le5000$
 $1\le pathLength\le1000$
Hint:
 If(InputSize = 1000~10^6), a tolerable upper bound of an algorithm would be $O(nlog(n))$
 If(InputSize = 10^7), a tolerable upper bound of an algorithm would be $O(n)$
 For this problem, if the input size is roughly $10^6<$M*N $<10^7$, the algorithm should be at least bounded by
 $O(MN log(MN))$ .
Output Specification:
Output the second shortest path in the form below:
1  Cost: cost 
If there’s no second shortest path exist:
 Print a prompt to indicate there’s no second shortest path
 Print the shortest path in the form below:
1  "But, the shortest path is" 
Sample:
 Input
1  5 6 
 Output
1  240 1 2 4 5 
Related Problems and Algorithms:
In general, this is an specialization of single source K Shortest Path Problem , where K=2.
Many different methods have been proposed to solve this problem, and there are two main variants of this problem:
For DiGraph with M edges and N vertices:
 Loopy Variant, which means backtrack is allowed.
 A solution was proposed by B. L. Fox in 1975
 $O(m + kn*log (n))$
 Fox, B. L. (1975). “Kth shortest paths and applications to the probabilistic networks”. ORSA/TIMS Joint National Meeting. 23: B263. CiNii National Article ID: 10012857200.
 A faster approach was proposed by David Eppstein
 $O(m + n*log (n)+k)$
 Eppstein, David (1998). “Finding the k Shortest Paths” (PDF). SIAM J. Comput. 28 (2): 652–673. doi:10.1137/S0097539795290477
 In this paper, he proposed that if the shortest path tree (in the form of heap) is given, we can find the kth shortest path in $O(m+n+k)$.
 A solution was proposed by B. L. Fox in 1975
 Loopless Variant, which means backtrack is not allowed.
 A wellknown solution is called Yen’s algorithm
 $O(kn(m +n log (n)))$
 Yen, J. Y. (1971). “Finding the kShortest Loopless Paths in a Network”. Management Science. 1 7 (11): 712–716. doi:10.1287/mnsc.17.11.712..
 A wellknown solution is called Yen’s algorithm
This problem, is the Loopy variant, which means an optimal time complexity can be achieved at $O(n*log (n))$, which has a desirable run time with given constraints.
Build Environment & To Run:
Building Environment:
 MacOS 12.0.1
 VSCode
 Compiler: Clang ++ 13.0
 C++ Standard = C++ 11
 ARM64 Platform (Apple Silicon)
Approach 1(Recommended)
Using cmake for crossplatform compile
Step1:
Download and install cmake
Step2:
The Cmake instructions (CMakeLists.txt) has been provided. You can modify it yourself.
Step3:
Open terminal/Powershell
Type in command as below
1  mkdir build 
Now you’re running the program.
The program will output result carries out by each algorithm and their total runtime, in order of decreasing time complexity.
Approach 2
Using VSCode C/C++ Extensions
1.Modify tasks.json file:
1  "args": [ 
2.Click the button on Run and Debug panel
Other IDE:
Import the source files, and set the C++ standard to C++11, better compile with Visual Studio 2019, or using Clang++.
Known Issue:
 GCC doesn’t support some C++ 11 features as of on Clang++, so if possible using clang++ instead.
 When using Visual Studio 2019 for compiling, a largest case of 5000 edges would throw error of std::vector memory limit. However, this won’t happen when compile with clang++.
INPUT MODE:
By default we set to __FILE_INPUT_ And Looptime to 1.
1 

USAGE ON MACROS:
 _SAMPLE_CASE_: The sample given by OJ.
 FILE_INPUT_: Get input from files.
 1 file case is provided to test the largest possible input.
 of size M=1000, N=5000
 _USER_INPUT_: Get input from command line
 Available Cases:
 _SAMPLE_CASE_1~6
 Available Graph Type:
 class DiGraph for directional graph
 class UGraph for undirectional graph
Chapter 2: Algorithm Specification Description
Graph Representation:
We use the multiList representation of graph, meaning the multiList[i] indicates all the edges which starts from vertex i.
Vertices on user interface level are numbered from 1 to n
Vertices in the multiList are numbered from 0 to n1
Since variable sized array is available in C++, we don’t need linked list for the multiList implementation, using vector<vector<std::pair<int,int>>> instead.
In the std::pair, the first one indicates the destination vertex and the second indicates the path length (or cost).
Type of the elements in the multiList:
1
2
3
4
5type(multiList) == vector<vector<std::pair<int,int>>> # this full multiList
type(multiList[0]) == vector<std::pair<int,int>> # this is all edges starting from a certain vertex
type(multiList[0][0]) == std::pair<int,int> # this is the single edge
pair.first # this is edge's destination
pair.second # this is edge's path lengthWe implemented two types of graph, undirected graph and directed graph.
 They differs quite little in this implementation. A undirected graph, in this case, is a specialization of the directed graph.
An API insertEdge() is implemented for edge insertion.
Check Connection:
Before we start to find the second shortest path, we have to firstly check if there’s a possible path from vertex 1 to vertex m. We implemented this by BreadthFirstSearch.
1  //keep a queue to store the vertices to be visited 
After above process, we check if vertex m has been visited, if not, means there’s no possible path from vertex 1 to vertex m, abort.
If vertex m has been visited, means there’s at least one path from vertex 1 to vertex m.
In this case, ShortestPath from 1 to m must exist.
Second Shortest Path:
In the Dijkstra’s algorithm, we find the shortest path by steps below:
We keep an table, keeps track of each vertex’s shortest Path Length from Start and its direct predecessor of in shortest path.
Each vertex is initialized as cost to infinity and predecessor to 1 as “Unmarked”
Each time visit the Unvisited Vertex Which Has The Shortest Path Length from Start
Compute its neighbors’ cumulative Path Length,
check if it’s shorter than the table’s records if it's shorter, update table with the **path length and predecessor**
After compute, Mark the Vertex as visited.
Dijkstra’s algorithm is an Greedy Algorithm, using local minimum to get global minimum.
 It’s possible to only record the direct predecessor of each vertex and be able to get the path from the table.
 The shortest path from vertex 1 to m is the global minimum, and each edge along this path is also the global minimum from vertex 1 to that vertex.
 An table may look like this
 It’s possible to only record the direct predecessor of each vertex and be able to get the path from the table.
Note that each step we have to find the Unvisited Vertex Which Has The Shortest Path Length from Start, If we do linear scan, the time complexity would be O(V^2). But if we keep a min heap, the time complexity would be O((V+E)log(E)).
Make Some Extension
To find the second shortest path, we simply keep another table, record the second shortest path from vertex 1 to vertex i. And we have to keep track of all of its predecessors (in implementation, a string), instead of a single direct predecessor, since a second shortest path isn’t necessarily made up by multiple second shortest subpaths.
We made some modification in the update part of the Dijkstra’s algorithm.
1  for v in adj(u): 
Also, to allow backtracking, each node can be pushed on to min heap multiple times. But for the second shortest path, the node in such path can appear at most twice.
This is obvious, if a path 1>3>1>2>1>4 contains a node appears more than twice (1 appears 3 times), there must exist 2 shorter paths where vertex 1 appear 1 and 2 times and reach 4, and thus it’s not a second shortest path.
The overall pseudocode looks like below:
1  minHeap.push(vertex1) 
If the second_shortest[vertexLast].cost=infinity, means there’s no second shortest path from vertex 1 to last vertex. In this case, we output the shortest path. A shortest path is ensured since we’ve done the BFS in advance.
Chapter 3: Testing Results
Case 1: Sample Case
1  DiGraph graph(5, 6); 
Result: Correct
Case 2: An Undirectional Graph
1  UGraph graph(10, 11); 
Result: Correct
Case 3: Two shortest paths exists, second shortest path requires backtracking
1  UGraph graph(3, 3); 
Result: Correct
Case 4: No second shortest path, but exist two shortest path of same length.
1  DiGraph graph(3, 3); 
Result: Correct
Case 5: No valid path from 1 to m
1  DiGraph graph(4, 3); 
Result: Correct
Case 6: Minimum Case
1  /* 
Result: Correct
Case 7: Maximum Case
1  /* 
Conclusion:
 The result seems acceptable so far, need some complex test cases for validation.
Chapter 4: Analysis and Comments
 M = number of Vertices
 N = number of Edges
1.Build Graph:
We keep an multiList by inserting all edges into the vector<vector<pair<int,int>>>
 Each insertion takes $O(1)$, the overall time complexity would be $O(N)$
Overall Time Complexity: $O(N)$
We keep an multiList, each element is consist of destination and cost, which is $O(1)$
the overall time complexity would be $O(N)$
Overall Space Complexity: $O(N)$
For Undirectional Graph, the only difference is that the insertion time and space taken by undirectional graph is twice as the directional one. But both are O(N) after all.
2.Check Connection:
 In this step each edge is visited at most once, each node is visited at most once.
 The enqueue and dequeue takes $O(1)$ time.
the overall time complexity would be $O(N)$
Overall Time Complexity: $O(M+N)$
Space Complexity :
A queue of $O(N)$ (at most contains all edges) is needed in this step.
Overall Space Complexity: $O(N)$
3.Second Shortest Path
We push each node to min heap at most twice (2M)
Each time a edge is popped
 We update table, which takes $O(1)$ time
Each pop or push takes $O(log(M))$ time
Overall Time Complexity: $O(Mlog(M))$
We keep two tables, each tables takes M elements, each elements contains a string (contains all predecessors, at most length O(N)) and a int (cumulative cost).
 Two tables occupies $O(2M*N)$ Space.
We also keeps an heap of max size $O(N)$, each node occupies $O(1)$ Space.
Overall Space Complexity: $O(M*N)$
OVERALL:
Overall Time Complexity: $O(N+Mlog(M))$
Overall Space Complexity: $O(M*N)$
Comments:
In the actual implementation of the constraint “each node is visited at most twice”, we use a slightly different approach based on the cumulative length, but they should have the same effect.
Although no hacking cases founded now, if things go wrong in some cases, the logic there needs a rewrite to be more accurate.
Extra: KShortest Path
If we extend the same technique to the K shortest path, we have to keep K table, which takes up $O(KMN)$ Space.
Each node can be pushed to heap at most K times, Which takes overall $O(N + KMlog (M))$ time.
Overall Time Complexity: $O(N+K*Mlog(M))$
Overall Space Complexity: $$O(KMN)$$
Appendix: Source Code (in C++11)
Djikstra.hpp
1 

Graph.hpp
1 

lab3.cpp
1 
