4 ms·

Introduction to Graph Theory: Finding The Shortest Path (Part 2)

77 points by mburst 14y ago

revelation 14y ago
Why would you call a Grid a Graph? A Graph consists of vertices and edges. That doesn't seem reasonable for something like "Introduction to Graph Theory".
- yk 14y ago
  And a grid consists also of vertices and edges ;) So a grid is certainly a very special graph, with a lot of additional structure, but it is also a lot easier to visualize than some abstract Markov chain.
  - gamegoblin 14y ago
    You are correct and I will expand: A grid graph is also known as a lattice graph, in which the graph can be embedded in R^n with a regular tiling. A square grid that is shown in the post is yet a more specific type of lattice graph.[1] Though the if one uses a square grid graph in which you move around from tile to tile, you are actually traversing the dual graph of the tiled visualization.[2] [1]http://en.wikipedia.org/wiki/Lattice_graph http://en.wikipedia.org/wiki/Lattice_graph [2]http://en.wikipedia.org/wiki/Dual_graph http://en.wikipedia.org/wiki/Dual_graph
  - yolesaber 14y ago
    What would a heuristic function look like for a "regular" graph (I.e. graphs as the data structures used for learning bfs, dfs, &c) then? I understand A* in terms of the grid what with the x and y distance, but how would implementing distance work in a non-grid graph? I feel as though it would just be taking the weights of edges and/or nodes. And if that's the case, then it essentially regresses to being Dijkstra's.
    - revelation 14y ago
      Any real world application for these algorithms will have the graph embedded in some kind of coordinate system. Euclidean distance is a popular heuristic given how it maps to the real world idea of "distance".
imslavko 14y ago
Why not Topcoder[1][2] tutorials? They are very inclusive, comprehensive and are not written in Ruby. [1]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2 http://community.topcoder.com/tc?module=Static&d1=tutori... [2]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3 http://community.topcoder.com/tc?module=Static&d1=tutori...
- dan1234 14y ago
  Is there a particular problem with them being written in Ruby?
  - imslavko 14y ago
    Probably not but I do not know anything in Ruby. I feel like C++ or Java is something everybody can read (a lot of people take them in University). My personal opinion.

77 points by mburst 14y ago

Why would you call a Grid a Graph? A Graph consists of vertices and edges. That doesn't seem reasonable for something like "Introduction to Graph Theory".

yk 14y ago
And a grid consists also of vertices and edges ;) So a grid is certainly a very special graph, with a lot of additional structure, but it is also a lot easier to visualize than some abstract Markov chain.
- gamegoblin 14y ago
  You are correct and I will expand: A grid graph is also known as a lattice graph, in which the graph can be embedded in R^n with a regular tiling. A square grid that is shown in the post is yet a more specific type of lattice graph.[1] Though the if one uses a square grid graph in which you move around from tile to tile, you are actually traversing the dual graph of the tiled visualization.[2] [1]http://en.wikipedia.org/wiki/Lattice_graph http://en.wikipedia.org/wiki/Lattice_graph [2]http://en.wikipedia.org/wiki/Dual_graph http://en.wikipedia.org/wiki/Dual_graph
- yolesaber 14y ago
  What would a heuristic function look like for a "regular" graph (I.e. graphs as the data structures used for learning bfs, dfs, &c) then? I understand A* in terms of the grid what with the x and y distance, but how would implementing distance work in a non-grid graph? I feel as though it would just be taking the weights of edges and/or nodes. And if that's the case, then it essentially regresses to being Dijkstra's.
  - revelation 14y ago
    Any real world application for these algorithms will have the graph embedded in some kind of coordinate system. Euclidean distance is a popular heuristic given how it maps to the real world idea of "distance".

imslavko 14y ago

Why not Topcoder[1][2] tutorials? They are very inclusive, comprehensive and are not written in Ruby. [1]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs2 http://community.topcoder.com/tc?module=Static&d1=tutori... [2]: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3 http://community.topcoder.com/tc?module=Static&d1=tutori...

dan1234 14y ago
Is there a particular problem with them being written in Ruby?
- imslavko 14y ago
  Probably not but I do not know anything in Ruby. I feel like C++ or Java is something everybody can read (a lot of people take them in University). My personal opinion.