Orca Challenge #3 - shortest path

Basic solution

Find the shortest path with DP optimization. This is my first/trivial solution for this challenge to find shortest path.

Time Complexity: O(N^2)

Memory Complexity: O(N)

Here, N is number of gateways.

Example Solution

Here is the solution for given example data.

Minimal distance: 37.3116

Example graph

View at GeoGebra

Best Solution

The number of gateways can be milion so that we have to find solution of time complexity O(N) or O(N * log(N))

I want to share my idea in the meeting.

While I will update my solution code.

Time Complexity: O(N)

Memory Complexity: O(N)

Algorithms: Dynamic Programming, Computational Geometry, Graph, Greedy

Idea: We only pass the endpoints of segments. It is the best solution.