Finding a 2D Array Path
I want to find the minimum weighted path between two indices of a 2D array. I tried to implement Dijkstra and A * shortest path algorithm but I couldn't. Below is an example. I want to give the start and end point of the path, and the path must be returned by the algorithm.
0 2 5 8 8 9
5 1 2 7 9 8
9 8 2 5 7 8
8 8 2 2 2 9
9 7 6 3 2 7
8 8 6 5 3 5
Can anyone recommend other algorithms or guide me about algorithms?
I've been working on this for a few days now and I don't think this is a difficult problem. But I am angry and cannot think of a goal. For example, I couldn't even figure out if the shortest path * and dijkstra has a direct connection with what I want to do. Or they work for 0 and 1 similar structures, which, if there is a wall, you cannot walk from there if you cannot. In my problem, you can navigate from anywhere, but I want to find the least cost path, etc.
source to share
Model your problem to "tailor" the design of the algorithms:
Try to create a graph from your grid first, this will help you understand these algorithms and implement them. Since both of these algorithms are for plots [that can simulate a grid], I think it will be easier for you to understand the algorithms when you implement them on "generic plots" and plot the plot for your specific problem.
Your graph will be G = (V,E)
where V = { (i,j) | (i,j) is a possible index) }
[all squares in the grid] and E = { (v,u) | v and u are adjacent vertices on the grid }
.
You also need an edge weighing function . w:E->N
... it will be w(u,v) = matrix[v.x][v.y]
[the value of the matrix according to v
].
Now add dijkstra in your facial language for the graph G
. The weight of your shortest path is the weight of the path found by dijkstra + matrix[source.x][source.y]
[because we didn't add this value to any edge on the shortest path].
To find the actual path , not just its weight, you will also need to hold map:V->V
which will map from each vertex to the found vertex. Similar to the idea described in this post .
Start with the simpler Dijkstram and then move on to A *:
I would start with dijkstra, not A *, since A * is basically an informed dijkstra, so you should be able to implement dijkstra before implementing A *. since this [dijkstra] is simpler.
Other Shortest Path Algorithms:
You should also be aware that there is another general Shortest Path algorithm - the famous Bellman-Ford [which can handle negative weights as well, unlike dijkstra].
source to share
Here's a sample I whipped up seems to work. To be more efficient, you need to implement a minimal heap when looking for the next shortest distance node.
private static int FindMin(int[,] indexWeights, Tuple<int, int> src, Tuple<int, int> dst)
{
List<Node> allNodes = new List<Node>(indexWeights.GetLength(0)*indexWeights.GetLength(1));
Node[,] graph = GenerateGraph(indexWeights, allNodes);
Queue<Node> queue = new Queue<Node>();
Node currentNode = graph[src.Item1, src.Item2];
// 0 ? or the weight value at the index? This was not too clear from your example
// Setting the starting distance to 0 means that a->b != b->a because the starting value
// at index b is not the same as the starting value at index a
currentNode.Distance = indexWeights[src.Item1, src.Item2];
queue.Enqueue(currentNode);
while (queue.Count > 0)
{
currentNode = queue.Dequeue();
currentNode.Visited = true;
if (currentNode.XCoord == dst.Item1 && currentNode.YCoord == dst.Item2)
break;
// Calculate tentative distances
foreach (Node neighbor in currentNode.Neighbors)
{
neighbor.Distance = Math.Min(neighbor.Distance,
currentNode.Distance + indexWeights[neighbor.XCoord, neighbor.YCoord]);
}
// Find the node with the minimum distance that hasn't been visited, and visit that next.
// A min-heap would be BEST for getting the next node, but I'll leave that as an exercise for you
Node nonVisitedMinNode = allNodes.Where(a => !a.Visited)
.Aggregate((currMin, currNode) => currMin.Distance < currNode.Distance ? currMin : currNode);
queue.Enqueue(nonVisitedMinNode);
}
return graph[dst.Item1, dst.Item2].Distance;
}
public class Node
{
public Node(int xCoord, int yCoord)
{
XCoord = xCoord;
YCoord = yCoord;
Distance = int.MaxValue;
Visited = false;
Neighbors = new List<Node>();
}
public int XCoord { get; set; }
public int YCoord { get; set; }
public int Distance { get; set; }
public bool Visited { get; set; }
public List<Node> Neighbors { get; set; }
}
public static Node[,] GenerateGraph(int[,] weight, List<Node> allNodes)
{
Node[,] nodes = new Node[weight.GetLength(0),weight.GetLength(1)];
for (int i = 0; i < weight.GetLength(0); i++)
{
for (int j = 0; j < weight.GetLength(1); j++)
{
nodes[i, j] = new Node(i, j);
allNodes.Add(nodes[i, j]);
}
}
// Couldn't think of a way to combine the two loops together to set neighbors
for (int i = 0; i < weight.GetLength(0); i++)
{
for (int j = 0; j < weight.GetLength(1); j++)
{
if (0 <= (i - 1))
nodes[i, j].Neighbors.Add(nodes[i - 1, j]);
if (weight.GetLength(0) > (i + 1))
nodes[i, j].Neighbors.Add(nodes[i + 1, j]);
if (0 <= (j - 1))
nodes[i, j].Neighbors.Add(nodes[i, j - 1]);
if (weight.GetLength(1) > (j + 1))
nodes[i, j].Neighbors.Add(nodes[i, j + 1]);
}
}
return nodes;
}
I couldn't think of some awkward way to generate the graph ... maybe it's too late here. In any case, you may need to customize the initialization of currentNode.Distance based on what we discussed in the comments. Is [0,0] 0 in your example because it is the starting index, or is it because the value starts at zero? If you provide another example where the start index is not 0, then it would be easier to understand the rules.
source to share
What you are looking for is the shortest path between two points in a 2D array, so either Dijkstra or * will work well for you. What you mentioned with 1s and 0s is nothing more than a pathfinding problem in 2D arrays, which is a more specific case of the above algorithms and can be implemented using simple BFS.
In terms of implementation, as mentioned, you need to decide how you will model your solution in a way that matches the design of the algorithm you are using. One of two possible ways:
- Convert 2D array to graph and run your algorithm between Source and Destination nodes.
- Represent each cell in such a way that you can run your algorithm without having to convert it to a graph.
Given that you go with Dijkstra, a sample implementation of this problem would be as follows:
//Controls the size of your 2D array. Made static for simplicity. Can be allocated dynamically.
#define MAX_NODES 10
/* Your 2D Point Structure. Stores information of each cell of your 2D array */
typedef struct Point
{
int x, y; //x and y co-ordinate of your point
int cost; //Cell actual cost
int cost_from_src; //Cell cost from the Source node. This gets updated when algorithm runs
unsigned int visited; //Keeps track of nodes that have been popped out of the Queue
struct Point *par; //Keeps track of Parent Node
}Point_t, *Point_p;
/* 2D array of Point structure */
Point_t adjMArr[MAX_NODES][MAX_NODES];
/* Finds SP in Weighted 2D-Matrix */
Point_p SPDijkstra(Point_t src, Point_t dest)
{
Queue_p q = NULL; // You can use your own implementation of a Queue
// Source is initially put into the Queue
adjMArr[src.x][src.y].cost_from_src = 0;
adjMArr[src.x][src.y].par = NULL;
q = push(q, adjMArr[src.x][src.y]);
while (!isEmpty(q))
{
Point_t pt = extractMin(q); // Get the point with minimum value of "cost_from_src" from the Queue
int x = pt.x, y = pt.y, new_cost, i;
adjMArr[x][y].visited = 1;
q = deleteQ(q, pt); // Delete this point from the Queue and mark it as visited. This point will not be visited again
if (dest.x == x && dest.y == y)
return &adjMArr[x][y]; // Destination Point
/*Check for all the neighbours of Point(x,y) and update the costs of its neighbours add them to the Queue*/
// Horizontal Left
if ((x - 1 >= 0) && y < MAX_NODES && !adjMArr[x - 1][y].visited)
{
new_cost = adjMArr[x][y].cost_from_src + adjMArr[x - 1][y].cost;
if (new_cost < adjMArr[x - 1][y].cost_from_src)
{
adjMArr[x - 1][y].cost_from_src = new_cost;
/* To keep track of parent so that once you reach the destination node, you can traverse all the way back to parent */
adjMArr[x - 1][y].par = &adjMArr[x][y];
q = push(q, adjMArr[x - 1][y]);
}
}
// Horizontal Right
if ((x + 1 < MAX_NODES) && y < MAX_NODES && !adjMArr[x + 1][y].visited)
{
new_cost = adjMArr[x][y].cost_from_src + adjMArr[x + 1][y].cost;
if (new_cost < adjMArr[x + 1][y].cost_from_src)
{
adjMArr[x + 1][y].cost_from_src = new_cost;
adjMArr[x + 1][y].par = &adjMArr[x][y];
q = push(q, adjMArr[x + 1][y]);
}
}
// Vertical Up
if ((y - 1 >= 0) && x < MAX_NODES && !adjMArr[x][y - 1].visited)
{
new_cost = adjMArr[x][y].cost_from_src + adjMArr[x][y - 1].cost;
if (new_cost < adjMArr[x][y - 1].cost_from_src)
{
adjMArr[x][y - 1].cost_from_src = new_cost;
adjMArr[x][y - 1].par = &adjMArr[x][y];
q = push(q, adjMArr[x][y - 1]);
}
}
// Vertical Down
if ((y + 1 < MAX_NODES) && x < MAX_NODES && !adjMArr[x][y + 1].visited)
{
new_cost = adjMArr[x][y].cost_from_src + adjMArr[x][y + 1].cost;
if (new_cost < adjMArr[x][y + 1].cost_from_src)
{
adjMArr[x][y + 1].cost_from_src = new_cost;
adjMArr[x][y + 1].par = &adjMArr[x][y];
q = push(q, adjMArr[x][y + 1]);
}
}
}
return NULL; // No path exists
}
source to share