The longest path between two points

Question

The problem is that i want to go from the top right to the down left with a maximum summation of digits,and i have to do that with just 12 moves,actually it's a chem. eng. problem but the brief way of solving was the points i mentioned,I know these types of problems have some theories in graph and some algorithms , but since I'm a chemical engineering student i'm not so much familiar with the graphs and related algorithms. I tried so hard to come up with an idea but i actually found none,i appreciate your ideas.

• note : we are allowed to do horizontal and vertical moves only

I used the answer and i got to this : (going from down left to right top,so moves are from down to top and left to right only,going from node 43 to node 7):

clc
clear

A = zeros(49) ;

A(8,1) = -3.02 ;

A(1,2) = -3.1 ;
A(9,2) = -2.04 ;

A(2,3) = -2.07 ;
A(10,3) = -2.09 ;

A(3,4) = -2.01 ;
A(11,4) = -2.04 ;

A(4,5) = -3.1 ;
A(12,5) = -3.03 ;

A(5,6) = -2.06 ;
A(13,6) = -2.05 ;

A(6,7) = -3.04 ;
A(14,7) = -2.05 ;

A(15,8) = -2.04 ;

A(8,9) = -3.04 ;
A(16,9) = -2.05 ;

A(9,10) = -2.02 ;
A(17,10) = -2.01 ;

A(10,11) = -3.1 ;
A(18,11) = -2.1 ;

A(11,12) = -2.09 ;
A(19,12) = -3.1 ;

A(12,13) = -2.08 ;
A(20,13) = -2.04 ;

A(13,14) = -2.03 ;
A(21,14) = -2.06 ;

A(22,15) = -3.05 ;

A(15,16) = -2.02 ;
A(23,16) = -2.09 ;

A(16,17) = -3.05 ;
A(24,17) = -2.07 ;

A(17,18) = -3.01 ;
A(25,18) = -2.08 ;

A(18,19) = -2.09 ;
A(26,19) = -3.03 ;

A(19,20) = -2.09 ;
A(27,20) = -2.02 ;

A(20,21) = -2.04 ;
A(28,21) = -3.05 ;

A(29,22) = -3.05 ;

A(22,23) = -2.07 ;
A(30,23) = -3.09 ;

A(23,24) = -3.05 ;
A(31,24) = -3.08 ;

A(24,25) = -2.01 ;
A(32,25) = -3.05 ;

A(25,26) = -2.01 ;
A(33,26) = -3.03 ;

A(26,27) = -3.04 ;
A(34,27) = -3.1 ;

A(27,28) = -3.05 ;
A(35,28) = -2.06 ;

A(36,29) = -2.03 ;

A(29,30) = -2.05 ;
A(37,30) = -3.05 ;

A(30,31) = -2.1 ;
A(38,31) = -3.06 ;

A(31,32) = -2.09 ;
A(39,32) = -2.09 ;

A(32,33) = -2.05 ;
A(40,33) = -2.07 ;

A(33,34) = -3.08 ;
A(41,34) = -3.02 ;

A(34,35) = -3.07 ;
A(42,35) = -3.04 ;

A(43,36) = -2.08 ;

A(36,37) = -2.05 ;
A(44,37) = -2.07 ;

A(37,38) = -2.08 ;
A(45,38) = -3.1 ;

A(38,39) = -3.03 ;
A(46,39) = -2.02 ;

A(39,40) = -2.09 ;
A(47,40) = -3.05 ;

A(40,41) = -3.09 ;
A(48,41) = -2.1 ;

A(41,42) = -3.1 ;
A(49,42) = -2.07 ;

A(43,44) = -2.08 ;

A(44,45) = -3.06 ;

A(45,46) = -2.01 ;

A(46,47) = -2.1 ;

A(47,48) = -2.02 ;

A(48,49) = -2.06 ;

G = digraph(A) ;

[path,d] = shortestpath(G,43,7) ;

But i get the wrong path length, matlab answer is 32.78 and the correct one must be 25.73 . the path i find is :

43 44 45 38 39 40 41 34 27 28 21 14 7

the answer path is :

43 36 29 30 31 24 25 18 19 20 13 14 7

Answer 1

With the limitations on the available moves, you can model your problem as a directed acyclic graph. As noted in the Wikipedia article on the Longest path problem you can solve this by transforming all of the edge weights w to -w and applying Dijkstra's shortest path algorithm on the resulting graph.

The fact that your graph is acyclic is critical here, because it means that there will be no negative-weight cycles that would cause Dijkstra's to fail.

---

In 2015b, MATLAB introduced new graph functions, including one called shortestpath. This is what we'll be using.

Graph representation

First you need to construct your graph. There are a couple of ways you can represent a graph and which one you use in this case is simply a matter of which one makes more sense to you. We're going to pass the information to MATLAB's digraph anyway, so as long as we give it acceptable input it'll work.

For either way, you first need to number your nodes (the grid intersections in your picture). How you number them is not important as long as you're consistent. I'll number the nodes 1-49: 1-7 on the top row, 8-14 on the second and so on until 43-49 for the bottom row. Here's a diagram of a few nodes in the top right corner of your grid that I'll use for demonstration purposes. (Remember we're changing all of the edge weights to their negative in order to find the longest path.)

              (-2.06)      (-3.04)
<--------  5 <--------  6 <--------  7
           |            |            |
           |(-3.03)     |(-2.05)     |(-2.05)
           |            |            | 
           v  (-2.08)   v  (-2.03)   v
<-------- 12 <-------- 13 <-------- 14
           |            |            |
           |(-3.10)     |(-2.04)     |(-2.06)
           |            |            | 
           v  (-2.09)   v  (-2.04)   v
<-------- 19 <-------- 20 <-------- 21
           |            |            |
           |            |            |
           |            |            |
           v            v            v

Adjacency matrix

One way to represent this is using an adjacency matrix. For n nodes, the adjacency matrix A is n x n. In our case, we'll have a 49 x 49 matrix. Each element in the matrix A(i, j) is 0 if there is no edge from node i to node j, or it is the weight of the edge. So the element A(7, 6) would contain -3.04 because that's the weight of the edge from node 7 to node 6. So, you just create the adjacency matrix

A = zeros(49, 49);

and start filling in the edge weights in the correct place.

A(7, 6) = -3.04;
A(14, 13) = -2.03;
A(13, 12) = -2.08;
and so on...

Edge list

Another way to represent the graph is using an edge list. Using this method, instead of a single n x n matrix you're going to use three vectors of length m, where m is the number of edges in your graph. The first vector s is the start (source) of each edge. The second vector t is the end (sink) of each edge. The last vector contains the weights for the corresponding edges. So, using the three edges from the adjacency matrix example, these matrices would look like this.

s = [ 7,    14,    13,    ...]
t = [ 6,    13,    12,    ...]
w = [-3.04, -2.03, -2.08, ...]

Here we've got the same edge from node 7 to node 6 with weight -3.04, and 14 to 13, etc.

Creating the digraph

To feed this information to MATLAB's graph algorithms you need to create the proper structure using the function digraph, either

G = digraph(A);

or

G = digraph(s, t, w);

depending on which representation you chose.

Use the shortestpath algorithm

Once you've got G, it's just a matter of calling shortestpath. Since we're using the negatives of the original weights, this will actually be the longest path. You also need to give it the start and end nodes for the path. Using my numbering this would be start_node = 7 and end_node = 43.

path = shortestpath(G, start_node, end_node);

This is the part where you might need to experiment a little bit. The shortestpath function actually has another parameter you can pass:

path = shortestpath(G, start_node, end_node, 'Method', <algorithm>);

That <algorithm> parameter allows you to select with shortest path algorithm will be used. If you don't specify the 'Method', from what I can see in the documentation it will default to 'Method', 'mixed' because of the negative edge weights. This should work just fine and give you the longest path. Another option that looks interesting is 'Method', 'acyclic' which might improve performance for larger graphs. If your grid is always going to be 7 x 7, then it probably won't matter much and you can just take the default.