Dijkstra's algorithm -- what does it mean by "vertex"

Discussion in 'iOS Programming' started by MythicFrost, Nov 7, 2011.

  1. MythicFrost macrumors 68040

    MythicFrost

    Joined:
    Mar 11, 2009
    Location:
    Australia
    #1
    Hi,

    I'm working on applying this to my own app and I'd like to know what it means by "vertex" aka "intersection"? Is the vertex for example 2,1 or 5,7 in my 2D int array?

    Thanks.
     
  2. iHutch105 macrumors member

    Joined:
    Aug 8, 2011
    #2
    A vertex can be a number of things. In this example I'd wager that you're looking the point where two line segments join.

    "Intersections" in that example are, I think, just metaphors for points or coordinates in the case. So, in your 2D array (which I presume is intended to represent some sort of 2D grid/graph), each set of coordinates (x,y) can be considered a vertex.

    So, if I'm reading into this right, yes; (2,1) and (5,7) are, along with any other coordinate location in your grid, examples of vertices.
     
  3. MythicFrost thread starter macrumors 68040

    MythicFrost

    Joined:
    Mar 11, 2009
    Location:
    Australia
    #3
    Thanks for that!

    So for example:

    Code:
    for each vertex v in Graph:            // Initializations
         3          dist[v] := infinity ;              // Unknown distance function from source to v
         4          previous[v] := undefined ;         // Previous node in optimal path from source
         5      end for ;
    dist[v] is actually dist[x][y] where x and y are the coordinates in my 2D grid?
     

Share This Page