Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

 3 TeXtify, typo edited Mar 12 at 8:58 dkaeae 4,65211 gold badge1111 silver badges2929 bronze badges It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not denseddense, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN)$$O(N \log N)$$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M)$$O(M)$$ complexity where M$$M$$ is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M$$M$$ numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. Note that, this is an O(M)$$O(M)$$ algorithm instead of O(N)$$O(N)$$. However, if the above assumptions are satisfied, it will work better than O(N)$$O(N)$$. So, it depends on how much your graph is denseddense. It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not densed, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN) complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M) complexity where M is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. Note that, this is an O(M) algorithm instead of O(N). However, if the above assumptions are satisfied, it will work better than O(N). So, it depends on how much your graph is densed. It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not dense, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an $$O(N \log N)$$ complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with $$O(M)$$ complexity where $$M$$ is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of $$M$$ numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. Note that, this is an $$O(M)$$ algorithm instead of $$O(N)$$. However, if the above assumptions are satisfied, it will work better than $$O(N)$$. So, it depends on how much your graph is dense. 2 added 181 characters in body edited Mar 11 at 22:06 one 1122 bronze badges It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not densed, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN) complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M) complexity where M is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. Note that, this is an O(M) algorithm instead of O(N). However, if the above assumptions are satisfied, it will work better than O(N). So, it depends on how much your graph is densed. It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not densed, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN) complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M) complexity where M is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not densed, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN) complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M) complexity where M is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order. Note that, this is an O(M) algorithm instead of O(N). However, if the above assumptions are satisfied, it will work better than O(N). So, it depends on how much your graph is densed. 1 answered Mar 11 at 21:59 one 1122 bronze badges It is possible assuming that your edge ID's are consecutive numbers (usually that's the case) and the graph is not densed, however, it will require extra amount of memory. Basic method is to sort the path after Dijkstra applied. In this case, a compare-based algorithm will require an O(NlogN) complexity, however in your case, you have an extra information: The edge ID's are consecutive numbers. Thus, you can use a non-comparison sorting algorithm such as counting sort with O(M) complexity where M is the number of edges. The method: Apply usual Dijkstra on the problem and find the shortest path. Create an array of M numbers initially assigned by -1. As traversing the shortest path, change the value of each traversed edge ID position in the array to 1. Scan the array for 1's to find the path in ascending order.