CODEWITHSUNDEEP
javaalgorithmgraph-theoryshortest-path
David
David

Reputation: 699

Finding shortest path in 2d array

I need to find the shortest path from top left to bottom right.

The Rules are it has to go from A to B to A to B etc.

See picture as example:

enter image description here

The expected output for the above picture is then 13.

I'm trying to implement this in java with a dijkstra algorithm for this but then got stuck. Is this the right way to go?

Upvotes: 2

Views: 1481

Answers (2)

Ankari
Ankari

Reputation: 619

If the goal is to find the shortest path from the top left corner to the bottom right corner (or between any arbitrary 2 points), dijsktra is one possible way to go, however you must correctly construct a graph from the input.

In this case I would go for a simple flood-fill algorithm. You can find several online resources explaining it including this video or this article, so I won't go in more details in this answer.

You can find the shortest route using only 2 matrices (one for your original array of letter and one for the distances) if you implement your rules correctly (A to B and B to A only).

Upvotes: 1

Gor
Gor

Reputation: 2908

You can use any graph traversal algorithm or any pathfinding algorithm. T, here are a lot of algorithms such as A*, Dijekstra, BFS, DFS ...

For example, let's take BFS, which finds the shortest path between 2 nodes of the graph. Suppose, your 2d array is a graph, where edges are on condition if the distance between 2 nodes is 1 and one of the nodes is A and second one is B. Read mode about BFS here (https://en.wikipedia.org/wiki/Breadth-first_search)

Just construct the graph from your matrix and implement BFS for the graph, or you can simply implement BFS for the array.

Upvotes: 1

Related Questions