Skip to content

A matlab function to solve shortest-path problems for lattice graph in a matrix format

Notifications You must be signed in to change notification settings

jay15summer/lattice-graph-shortest-path

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 

Repository files navigation

lattice-graph-shortest-path

Description

The program solves the shortest-path problem for a 2D lattice graph (grid graph)
which can be represented in a matrix format. 
For example, a 4-by-4 lattice graph can be represented by a 4-by-4 matrix. 
(One entry corresponds to one grid point of the lattice graph).
At every grid point, one can travel to its up/down/left/right side grid point.
The arc-length (weight) between neightboring grids is calculated by a function
of corresponding entries' values in the matrix.
Assume the matrix is:  
Matrix = [1 4 7 6;
          6 5 4 3;
          1 5 2 2;
          1 4 6 1]. 
Also assume the traveling cost from entry i to entry j is only determined 
by the entry value j,(e.g., weight function is wf = @(i,j)(0.*i + 1.*j)). 
We can quickly find out that the shortest-path traveling from node(1,1) to
node(4,4) is (1,1)-->(2,1)-->(3,1)-->(3,2)-->(3,3)-->(3,4)-->(4,4), the
total traveling distance is 6+1+5+2+2+1=17.
The above type of problem can be solved by this program conveniently.
See the following result:  
Path = [1     4     7     6;
        |
        V
        6     5     4     3;
        |
        V
        1 --> 5 --> 2 --> 2;
                          |
                          V
        1     4     6     1]. 

Other more complex lattice-graph-shortest-path problems can also be solved by this program. 

Installation

Download and add 'gridmatrixshortestpath.m' and 'main.m' to your path (folder).

Usage

  1. 'gridmatrixshortestpath.m':
    a matlab function to solve shortest-path problems for lattice grids in a matrix format.
Input: 
      GridMatrix: A matrix representing the lattice graph (m-by-n)
      wf:         Weight fucntion to calculate the arc length traveling
                  between neighboring grids
      start/stop: the indexes of start and target grid points
                  e.g.,start = [1 2](p-by-2); stop = [7 9](p-by-2)
--------------------------------------------------------------------------
Output:
     dist:     the shortet distance between start and stop (p-by-1)
     pos_in_M: the shortest-path (q-by-2-by-p)
  1. 'main.m':
    an example/demo of how to implement gridmatrixshortestpath.m.

About

A matlab function to solve shortest-path problems for lattice graph in a matrix format

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages