search

Yonaba / Jumper

Fast, lightweight and easy-to-use pathfinding library for grid-based games
http://yonaba.github.io/Jumper
MIT License
607 stars 122 forks source link

Add search algorithm : SPFA #28

Open Yonaba opened 10 years ago

Yonaba commented 10 years ago

Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes single-source shortest paths in a weighted directed graph. The algorithm is believed to work well on random sparse graphs and is particularly suitable for graphs that contain negative-weight edges.

Pseudo-code for procedure Shortest-Path-Faster-Algorithm(G, s):

for each vertex v ≠ s in V(G)
  d(v) := ∞
  d(s) := 0
  offer s into Q
  while Q is not empty
    poll Q
    for each edge (u, v) in E(G)
      if d(u) + w(u, v) < d(v) then
        d(v) := d(u) + w(u, v)
          if v is not in Q then
            offer v into Q