dijkstra

[MattC98]

Given N and an NxN matrix , find the shortest path from (1, 1) to (n, n)
example :
Input :
3
1 2 5
1 3 1
0 8 1
Output : 7
explanation :
1 (1,1) + 1 (2,1) + 3 (2, 2) + 1 (2, 3) + 1 (3, 3) = 7
can someone tell me how to implement dijkstra, Ive only studied graphs for 2 days..

[punksheep]

Hi MattC98,
Thank you for that "algorithm", I never implemented Dijkstra everbut in your example, correct me if I'm wrong, the problem is just a kind of "data propagation". And then selection.

Let me explain and just stop me (lol you can't muahaha) when I'm absolutely out of my shoes.
The challenge here is to determine the cost of the path when you traverse the square matrix from one corner to the other. This simplifies the "research" a lot. Because now you know where to start and where it ends.

Let's try this algorithm and then we'll code it :
1) start à corner (1,1) : the cost is that element e(1,1). Here it's the value 1 itself.
2) for the precedent "square" (level i), propagate the cost to the i+1 square level.
3) stop when the square is size N for an NxN matrix
4) the find the shortest path starting in reverse by looking at the cell (N,N)

How to propagate...
Let's consider cell(x,y) as the cell taken at line x and column y. For example, the cell(3,1) here is value "0" (zero).
We have a i*i square already cost-computed
The objective is to compute the remaining two lines of element long of (i+1) cell : the vertical and horizontal line of that square of size (i+1)*(i+1) : that precisely i cost to compute horizontaly and i costs vertically + a last cost for the element e(i+1, i+1).

The "neighbor" style here is evidently a 4-neighbor type : that is, you cannot move in diagonal : only veritcal or horizontal.

For example : the current sub-square is size 2x2 and we want to compute the costs for the square of size 3x3. Based on the example given of the 3x3 square,
1) the first step, the square of size 1x1 is the element 1 (the cost is 1)
2) the square 2x2 is every three cells with addition of the lowest cost from a neighbor cell of the square 2x2

1 3
2 ?

To a (i+1)-level cell, there is only 3 maximum i-level-neighbor. We take the least cost and sum that to the cell itself.
So here :

cell<i+1>(1,2) = 3 = cell<i>(1,2) + cost(1,1) = 2 + 1
cell<i+1>(2,1) = 2 = cell<i>(2,1) + cost(1,1) = 1 + 1
cell<i+1>(2,2) = 4 = cell<i>(2,2) + cost(1,1) = 3 + 1

The last corner sell of the current square is the minimum addition of cost with the two last computed cells. Here 2 and 3. Evidently 2 is less than 3. We add the cost of cell(2,2) which is 3, to 2. That gives us a cost of 5. So that cost square of size 2

1 3
2 5

3) the square 3x3 is obtained the same way : compute the cost of each 2 cells in horizontal, then the 2 cells in vertical and the last cell(3,3).

1  3 8
2  5 6
2 10 ?

4) the element (3x3) has two neighbor with cost 6 and 10. Thus 6 + 1 = 7. And the square of size 3x3 is the final one since (in this example) we took a 3x3 square. Final cost square =

1  3  8
2  5  6
2 10 7

5) the final minimum cost is 7 and if we have store the path each step for each cell, then tracing back the path gives us from cell(3,3) to cell(1,1) ==>

cell(3,3), cell(2,3) cell(2,2) cell(2,1) cell (1,1)

.

And the algorithm is completed with that path forming a kind of "aleph symbol".

Algorithm
1) start at cell(1,1) and i = 1
2) propagate to size i+1 with two loops :
2.1) one for the i horizontal element (i+1, y) for y = 1 to i+1
2.2) one for the i vertical element (y, i+1) for y = 1 to i+1
2.3) compute last element cost cell(i+1, i+1)
2.4) increment i (because cost-square of size i+1 is now computed completedly)
3) continue until i reaches the value N
4) trace back from cell(N,N) back to cell(1,1) to determine the path

Note : the path contains exactly 2N+1 element because of the 4-neighbor movement = horizontal and vertical only, no diagonal.

Algorithm to compute the cost of cell<i+1>(i,j)
That cell has exactly two cell of level<i> "under" it :
a) the vertical (upward) cell and
b) the horizontal (leftward) cell neighbor
Take the least cost, sum it to the current cell<i+1>(i,j) and store the least-cost neighbor for future reference.

Data structure
We need exactly NxN cells (objects) containing :
1) the cost of the actual matrix : that is the original values themselves
2) the coordinate of the least-cost-neighbor of level i-1
For example, we can take the :

class Matrix
{
public:
	int size;
	std::vector<std::vector<Cell>> lcCell;
	std::vector<Cell> path;
};

The code is a bit long so, here's the main step of the computation :

void Matrix::computeCostAndPath()
{
	for(auto level = 2; level <= size; ++level)
	{
		computeStep1VerticalLevelCost(level);
		computeStep2HorizontalLevelCost(level);
	}
	computePath();
}

You can get the full one file code here https://www.punksheep.com/partage/C++/dijkstra_lowest_cost_path_in_matrix.zip

Have fun and tell me if you don't understand ;)
The code is not clean, I've focused more on the functionality than the OOP style so there's no specific constructor etc. And I'm helped a lot by C++ 2017 ^_^~

[MattC98]

thanks