book-given solution is here (ver 1.2.1: prob 16.11/ ver 1.5.3: prob 22.49): https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/RoadNetwork.java
i have my alternative solution coded up and tested using the above test code, but it’s going to be way easier to understand just explaning the algorithm, because it’s rather simple.
the book-given solution is using floyd-warshall whose time complexity (as described in book) is O(n^3).
the book on the side also mentions single-source dijkstra has time complexity of O(n lg n + m).
for alternative solution, you only need to run dijkstra twice.
- with source == el paso
- with source == corpus christi // valid because graph is undirected.
(side-note: if the graph is directed (it’s not), we can still use dijkstra’s algorithm for #2; just temporarily reverse the edges when computing #2 which would turn single-destination problem back to single-source shortest path prob)
running dijkstra twice still has time complexity of O(2(n lg n + m)) -> O(n lg n + m).
with that, for each proposed highway section ( cityA, cityB, distance),
// pseudo-code
for (HighwaySection hs : sections) {
proposal1 = hs.cityA.minDistanceElPaso + hs.distance + hs.cityB.minDistanceCorpus;
proposal2 = hs.cityB.minDistanceElPaso + hs.distance + hs.cityA.minDistanceCorpus;
proposal = min(proposal1, proposal2);
if (proposal < minProposal) {
minProposal = proposal;
minProposalSection = hs;
}
}
and at the end, return minProposalSection.
that loop should have time compelexity of k (# of proposals)
so overall time complexity is,
O (n lg n + m + k); // k <= n(n-1) / 2
which should be better than book-given solution complexity of
O (n^3 + k); // == O(n^3)
let me know if there was something wrong in my time complexity analysis… at least, i implemented the entire thing, and ran the test code and it always matched the given solution.
