On 14Aug2017 12:10, Michael C <mysecretrobotfact...@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 <c...@cskk.id.au> (formerly c...@zip.com.au)
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
