by Zoran Horvat

May 21, 2015

A matrix of integer numbers is given, each cell representing a weight. Write a function which finds a continuous path connecting any element of the first row with any element of the last row in the matrix, such that the sum of elements along the path is minimized. Function should receive a matrix and return

When matrix is drawn in a usual way, path walks strictly downwards through it. From each cell it is legal to move to one of the three cells directly beneath it, as shown in the following picture.

For example, take a look at the following matrix:

The red line is laid over the minimum weight path. Sum of weights on this path is 10. For this particular matrix, the function should return array [4, 3, 4, 3, 2], because the path consists of elements in locations (1, 4), (2, 3), (3, 4), (4, 3) and (5, 2). Note that 1-based row and column indices are used.

Despite the somewhat boring statement, this problem occurs quite often in real life. A walker could try to find the path through tall grass, such that the grass is shortest along the selected route. The problem is also similar to the lightning effect. Roughly speaking, lightning finds the lowest resistance path from the cloud towards the earth.

We can approach this problem incrementally. How would it go if the matrix only had one row? In that case, the minimum weight path would be the minimum weight element from the first row.

How would it go if we added one additional row? In that case, we could find minimum path to a given element in the second row by finding the lowest value in the first row and then just stepping to the second row from that element.

And so the analysis goes on by adding more and more rows to the matrix, until the matrix is fully populated. The result of this operation is another matrix, fully populated by minimum weights of paths to each of the elements.

Picture below shows two matrices. The one on the left is the matrix of weights. The one on the right is populated by calculating minimum path weight to each of the cells. As you can see, many paths die out because a better candidate appears down along the way. In the end, one path prevails, having minimum total weight, and that path will be produced as the result of the algorithm.

After the path weights matrix is built, we can find the minimum value on the last row. That value – 10 in the example above – will indicate the weight of the winning path. It still doesn’t tell us which elements fall on the path. At that point, we can look at the elements right above the winning element and see from which element we could arrive to the winner in order to reach its weight. In the example above, that is another element with path weight 10. We continue further, moving up the matrix and finding predecessors for each of the elements, until the first row is hit. At that point we will have the full path reconstructed.

Time required to traverse the matrix and build minimum weight paths matrix is proportional to number of elements in the matrix. Time required to figure out the minimum weight path consists of two steps. In the first step we are finding the winning element in the last row, which takes time proportional to number of columns. The second step is to backtrack the winning elements until we reach the first row in the matrix, which requires time proportional to number of rows of the matrix.

Total time of the algorithm is then O(MN + M + N) = O(MN), where M and N are dimensions of the matrix.

Here is the function which accepts the weights matrix and builds the path weights matrix:

```
function BuildPathWeights(weights, rowsCount, colsCount)
-- weights – matrix containing weights
-- rowsCount – total number of rows in the matrix
-- colsCount – total number of columns in the matrix
-- returns matrix with path weights
begin
pathWeights = new matrix rowsCount x colsCount
for col = 1 to colsCount
pathWeights(1, col) = weights(1, col)
for row = 2 to rowsCount
begin
for col = 1 to colsCount
begin
candidateCol = col
if col > 1 AND
pathWeights(row – 1, col – 1) < pathWeights(row – 1, candidateCol) then
candidateCol = col - 1
if col < colsCount AND
pathWeights(row - 1, col + 1) < pathWeights(row - 1, candidateCol) then
candidateCol = col + 1
pathWeights(row, col) = pathWeights(row - 1, candidateCol) + weights(row, col)
end
end
return pathWeights;
end
```

This function simply walks through the matrix, row-wise. In each cell it visits it has up to three candidate cells right above from which the minimum weight path could arrive to the current cell. The function simply chooses the best fit candidate and sets minimum weight path for the current cell.

Once the path weights matrix if built, we can reconstruct the minimum weight path through the whole matrix. That is what the next function does:

```
function ExtractMinimumWeightPath(weights, pathWeights, rowsCount, colsCount)
-- weights – matrix of weights
-- pathWeights – matrix produced by BuildPathWeights function
-- rowsCount – number of rows in the matrix
-- colsCount – number of columns in the matrix
begin
path = new array with rowsCount elements
col = 1
for i = 2 to colsCount
if (pathWeights(rowsCount, i) < pathWeights(rowsCount, col) then
col = i
row = rowsCount
repeat
path(row) = col
if col > 1 AND
pathWeights(row – 1, col – 1) + weights(row, col) = pathWeights(row, col) then
col = col – 1
else if col < colsCount AND
pathWeights(row – 1, col + 1) + weights(row, col) = pathWeights(row, col) then
col = col + 1
row = row - 1
until row = 0
path(1) = col
return path;
}
```

At the beginning, this function first identifies the overall winner – the element of the last row which has the lowest path weight. After that, the function backtracks the minimum weight path until the first row is reached.

In the end, it only remains to tie these two functions together into a working solution:

```
function GetMinimumPath(weights, rowsCount, colsCount)
-- weights – matrix with weights
-- rowsCount – number of rows in the matrix
-- colsCount – number of columns in the matrix
begin
pathWeights = BuildPathWeights(weights, rowsCount, colsCount)
path = ExtractMinimumWeightPath(weights, pathWeights, rowsCount, colsCount)
return path
end
```

This function simply delegates work to the two specialized functions we have prepared earlier. Net result is the array containing column indices from the minimum weight path, as requested in the problem statement.

Below is the complete console application implementation in C# which solves the problem of finding minimum weight path through the matrix.

```
using System;
namespace MinWeightPath
{
class Program
{
static Random rnd = new Random();
static int[,] InitializeMatrix(int n, int m)
{
int[,] matrix = new int[n, m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
matrix[i, j] = rnd.Next(10);
return matrix;
}
static int[] GetMinimumPath(int[,] weights)
{
int[,] pathWeights = BuildPathWeights(weights);
int[] path = ExtractMinimumWeightPath(weights, pathWeights);
return path;
}
private static int[,] BuildPathWeights(int[,] weights)
{
int rowsCount = weights.GetLength(0);
int colsCount = weights.GetLength(1);
int[,] pathWeights = new int[rowsCount, colsCount];
for (int i = 0; i < colsCount; i++)
pathWeights[0, i] = weights[0, i];
for (int row = 1; row < rowsCount; row++)
{
for (int col = 0; col < colsCount; col++)
{
int candidateCol = col;
if (col > 0 &&
pathWeights[row - 1, col - 1] < pathWeights[row - 1, candidateCol])
candidateCol = col - 1;
if (col < colsCount - 1 &&
pathWeights[row - 1, col + 1] < pathWeights[row - 1, candidateCol])
candidateCol = col + 1;
pathWeights[row, col] = pathWeights[row - 1, candidateCol] + weights[row, col];
}
}
return pathWeights;
}
private static int[] ExtractMinimumWeightPath(int[,] weights, int[,] pathWeights)
{
int rowsCount = weights.GetLength(0);
int colsCount = weights.GetLength(1);
int[] path = new int[rowsCount];
int col = 0;
for (int i = 1; i < colsCount; i++)
if (pathWeights[rowsCount - 1, i] < pathWeights[rowsCount - 1, col])
col = i;
int row = rowsCount - 1;
do
{
path[row] = col + 1;
if (col > 0 &&
pathWeights[row - 1, col - 1] + weights[row, col] == pathWeights[row, col])
col = col - 1;
else if (col < colsCount - 1 &&
pathWeights[row - 1, col + 1] + weights[row, col] == pathWeights[row, col])
col = col + 1;
row--;
}
while (row > 0);
path[0] = col + 1;
return path;
}
static void PrintPath(int[,] matrix, int[] path)
{
int rowsCount = matrix.GetLength(0);
int colsCount = matrix.GetLength(1);
int sum = 0;
for (int row = 0; row < rowsCount; row++)
{
Console.WriteLine();
for (int col = 0; col < colsCount; col++)
{
string prefix = " ";
string suffix = " ";
if (col == path[row] - 1)
{
sum += matrix[row, col];
prefix = "[";
suffix = "]";
}
Console.Write(" {0}{1}{2} ", prefix, matrix[row, col], suffix);
}
}
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("Sum of weights: {0}", sum);
Console.WriteLine();
}
static void Main(string[] args)
{
while (true)
{
Console.Write("Enter number of rows (0 to exit): ");
int rowsCount = int.Parse(Console.ReadLine());
if (rowsCount <= 0)
break;
Console.Write("Enter number of columns: ");
int colsCount = int.Parse(Console.ReadLine());
int[,] matrix = InitializeMatrix(rowsCount, colsCount);
int[] path = GetMinimumPath(matrix);
PrintPath(matrix, path);
}
}
}
}
```

When console application listed above is run, it produces the following output:

` ````
Enter number of rows (0 to exit): 3
Enter number of columns: 5
9 7 8 [3] 8
8 6 [1] 2 3
4 7 5 [0] 8
Sum of weights: 4
Enter number of rows (0 to exit): 5
Enter number of columns: 7
6 4 8 9 1 [0] 3
3 0 5 9 [3] 4 2
3 0 8 1 [1] 3 3
4 2 0 7 [0] 9 3
7 5 9 9 3 [0] 3
Sum of weights: 4
Enter number of rows (0 to exit): 5
Enter number of columns: 10
5 1 6 4 9 8 [0] 3 0 1
8 4 7 2 8 4 [2] 5 3 7
6 7 7 2 9 6 6 [0] 8 4
3 2 2 6 1 9 4 [2] 6 7
2 8 0 7 6 6 6 [1] 2 9
Sum of weights: 5
Enter number of rows (0 to exit): 10
Enter number of columns: 10
1 8 1 7 6 [1] 2 5 8 6
9 6 6 4 8 [2] 7 1 4 0
1 1 9 5 [0] 7 8 6 9 7
8 5 5 8 [1] 3 7 3 3 8
1 8 9 3 [2] 6 4 0 5 6
7 0 9 3 0 [0] 9 5 7 8
2 5 6 0 7 3 [0] 8 3 4
5 4 7 6 9 3 [1] 5 3 4
2 8 1 2 9 8 5 [2] 7 1
4 1 6 4 6 5 [1] 9 5 8
Sum of weights: 10
Enter number of rows (0 to exit): 20
Enter number of columns: 10
3 2 9 2 9 [0] 6 9 4 1
8 7 8 5 9 [0] 4 4 3 0
9 4 6 2 7 [3] 4 4 5 2
0 7 0 8 5 6 [2] 9 2 2
5 7 5 8 3 2 [0] 5 8 4
6 2 5 9 5 9 [6] 6 4 5
5 1 4 2 1 [0] 7 0 0 3
8 4 1 1 5 [2] 8 7 8 5
3 9 5 0 6 7 [2] 1 2 6
0 5 4 6 6 [3] 3 3 7 2
4 0 4 4 6 [1] 0 4 3 3
0 8 7 9 [2] 5 6 3 5 3
8 6 7 3 3 [2] 9 5 4 1
8 5 0 6 [0] 3 5 0 4 4
7 7 7 8 6 [1] 8 5 4 1
7 9 7 3 [4] 8 2 1 1 4
2 5 0 [1] 4 4 8 1 8 9
0 5 9 [0] 6 0 8 9 7 2
4 4 [0] 3 4 9 7 6 2 2
1 [4] 9 9 2 1 7 5 3 1
Sum of weights: 33
Enter number of rows (0 to exit): 0
```

If you wish to learn more, please watch my latest video courses

This course begins with examination of a realistic application, which is poorly factored and doesn't incorporate design patterns. It is nearly impossible to maintain and develop this application further, due to its poor structure and design.

As demonstration after demonstration will unfold, we will refactor this entire application, fitting many design patterns into place almost without effort. By the end of the course, you will know how code refactoring and design patterns can operate together, and help each other create great design.

More...

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented and functional development style and clean coding practices and techniques that improve longevity of complex business applications.

- Refactoring to Design Patterns
- Mastering Iterative Object-oriented Programming in C#
- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Making Your Java Code More Object-oriented
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design

- The Fast Pencil Fallacy in Software Development
- Favoring Object-oriented over Procedural Code: A Motivational Example
- From Dispose Pattern to Auto-disposable Objects in .NET
- What Makes Functional and Object-oriented Programming Equal
- Overcoming the Limitations of Constructors
- Does the Command Pattern Require Undo?
- More...