http://www.codinghelmet.com/ Wear a helmet. Even when coding. Follow Zoran Horvat @zoranh75
exercises > minimum-weight-path-through-matrix

# Exercise #29: Finding Minimum Weight Path Through Matrixby Zoran Horvat@zoranh75May 21, 2015

## Problem Statement

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.

## Problem Analysis

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.

## Solution

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.

## Implementation

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): ");

if (rowsCount <= 0)
break;

Console.Write("Enter number of columns: ");

int[,] matrix = InitializeMatrix(rowsCount, colsCount);

int[] path = GetMinimumPath(matrix);

PrintPath(matrix, path);

}

}
}
}
```

## Demonstration

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
```

Published: May 21, 2015; Modified: May 14, 2015

ZORAN HORVAT

Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on object-oriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Watch Zoran's video courses at pluralsight.com (requires registration):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More...

Tactical Design Patterns in .NET: Control Flow

Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More...

Improving Testability Through Design

This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More...