How to apply Pathfinding in a node structure?

Question

How to apply Pathfinding in a node structure?

Navigation

#1 by (3 votes)

6

I have a structure of nodes that represent my pages and their links, for example, from page A I can go to page B or page C. Besides that I can have page A pointing to B pointing to C pointing back to A. What I need to do is to determine a source page and a destination page, and display only the related nodes, for example from A, get to H.

What algorithm is used to find this type of path?

asked by anonymous 13.01.2017 / 12:43

1 answer

App.config how to use 'ConnectionString' encrypted Time Zone JavaScript

score 3 · Answer 1

There are several algorithms for this purpose, among them:

Dijkstra's

Here's an example of pseudo-code taken from the link:

function Dijkstra(Graph, source):

       create vertex set Q

       for each vertex v in Graph:             
           dist[v] ← INFINITY
           prev[v] ← UNDEFINED
           add v to Q

      dist[source] ← 0

      while Q is not empty:
          u ← vertex in Q with min dist[u]
          remove u from Q 

          for each neighbor v of u:           
              alt ← dist[u] + length(u, v)
              if alt < dist[v]:
                  dist[v] ← alt 
                  prev[v] ← u 

      return dist[], prev[]

D * D-Star Algorithm

Algorithm Any-angle path planning

A * A-Star Algorithm