[Tutor] "Path tree"

[Cameron Simpson]

On 14Aug2017 12:10, Michael C <mysecretrobotfactory at gmail.com> wrote:
>http://imgur.com/a/CwA2G

Ok. So you have a graph like this:

  1 -- 2 -- 3 -- 4
       |
  7 -- 5 -- 6 -- 8

Have a read of a graph theory textbook. Also, wikipedia has an article on 
finding the shortest path through a graph:

  https://en.wikipedia.org/wiki/Shortest_path_problem

which references several algorithms.

You could pick one (eg Dijkstra's algorithm) and try to implement it. For a 
graph this small you could try your own and do something rather brute force; in 
larger graphs efficiency becomes very important.

You will need to express the graph as a data structure in your code, with a 
data structure that expresses which nodes connect to each other node. Typically 
this often includes weights for the edges and a direction, but your graph has 
no weights (cost of traversing a particular edge) and is undirected (you can 
traverse an edge in either direction). It is also "simply connected" - there 
are no loops. All these things make your task simpler.

You can express a graph as a direcionary with keys being your node numbers 
(i.e. 1, 2, 3 etc) and the values being a list of the other nodes to which each 
connects. Eg:

  graph = {
    1: [2],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [7, 6],
    6: [5, 8],
    7: [5],
    8: [6]
  }

The you need to write code that starts somewhere (4 in your example) and moves 
to other nodes until it reaches the target node (8 in your example). You can 
see which other nodes are reachable your current from the dictionary above. You 
need to keep some kind of record of which nodes you have visted (i.e. that is 
the path).

See if that gets you started. For debugging, make your program print out what 
node it is at as it traverses the graph - that will be helpful to you in 
figuring out what is working and what is not.

Cheers,
Cameron Simpson <cs at cskk.id.au> (formerly cs at zip.com.au)