We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Dijkstra: Shortest Reach 2
Dijkstra: Shortest Reach 2
Sort by
recency
|
467 Discussions
|
Please Login in order to post a comment
js (solution using priority Q / heap)
js
what is the problem with this algorithm I just can't get around the fact that my algorithm seems right and yet only 2 test cases are passing
If you couldn't pass Test Case 7 (like most people did), it's probably not your fault for poorly implementing Dijkstra's algorithm.
As people have said, Test Case 7 includes a lot of duplicate edges, which is a recipe for disaster if your Dijkstra implementation does not account for edge duplications (which understandably most people didn't expect to have to do).
This, along with the rather slow I/O and loop processing of certain languages, makes Test Case 7 near impossible to pass if you go with Dijkstra. Some have had success with Bellman-Ford instead, but that's not what this problem meant for you to do (it literally has "Dijkstra" in its title).
An alternative workaround (and one that I deem legit and not cheating, seeing how absurd Test Case 7 is) is to optimize the reading of the stdin input in the program's entry point (aka. the 'main' function).
Most importantly, store the edges in a Set when reading stdin instead of the default data structure (in Java's case a List), and then recast it back when appropiate.
After that, you can look for more language-specific optimizations to the stdin reading if you want. In my case (Java 8) I removed the
String.replaceAll("\\s+$", "")
that removes trailing spaces which recompiles the RegEx into aPattern
each time it is called which is unnecessarily horribly costly since tests on HackerRank don't have trailing spaces anyways.Here's the resulting part of modified
main
code for Java 8My Java Solution, using Bellman - Ford Queue Based for complexity O(|E| + |V|) in typical case and O(|E||V|) in worst case (but rare): https://github.com/tuphan22028238/DSA/blob/main/BT13/03_Dijkstra/BellmanFord.java