Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of uppercase, lowercase, numbers, and special characters (such as @*&#).
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Certifications

Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

Invoice

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File
v4.3
Search
    中文EN
    v4.3

      Shortest Path Faster Algorithm (SPFA)

      ✓ File Writeback ✕ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

      Overview

      The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman–Ford algorithm which computes the shortest path between a source node and all reachable nodes (i.e., single-source shortest paths) in a graph. The algorithm is particularly suitable for graphs that contain negative-weight edges.

      The SPFA algorithm was first published by E.F. Moore in 1959, but the name, “Shortest Path Faster Algorithm (SPFA),” was given by FanDing Duan who rediscovered the algorithm in 1994.

      Concepts

      Shortest Path Faster Algorithm (SPFA)

      Given a graph G = (V, E) and a source node s∈V, array d[] is used to store the distances of the shortest paths from s to all nodes. Initialize all elements in d[] by infinity except for d[s] = 0.

      The basic idea of SPFA is the same as the Bellman–Ford algorithm in that each node is used as a candidate to relax its adjacent nodes. The improvement over the latter is that instead of trying all nodes unnecessary, SPFA maintains a first-in, first-out queue Q to store candidate nodes and only adds a node to the queue if it is relaxed.

      The term relaxation refers to the process of updating the distance of a node v that is connected to node u to a potential shorter distance by considering the path through node u. Specifically, the distance of node v is updated to d[v] = d[u] + w(u,v), where w(u,v) is the weight of the edge (u,v). This update is performed only if the current d[v] is greater than d[u] + w(u,v).

      At the begining of the algorithm, all nodes have the distance as infinity except for the source node as 0. The source node is viewed as first relaxed and pushed into the queue.

      During each iteration, SPFA dequeues a node u from Q as a candidate. For each edge (u,v) in the graph, if node v can be relaxed, the following steps are performed:

      • Relax node v: d[v] = d[v] + w(u,v).
      • Push node v into Q if v is not in Q.

      This process repeats until no more nodes can be relaxed.

      The steps below illustrate how to compute the SPFA with source node A and find the weighted shortest paths in the outgoing direction:

      Considerations

      • The SPFA can handle graphs with negative edge weights under the conditions that (1) the source node cannot access any node within a negative cycle, and (2) the shortest paths are directed. A negative cycle is a cycle where the sum of the edge weights is negative. When negative cycles are present or the shortest paths are undirected when negative weights exist, the algorithm will output infinite results. This happens because it repeatedly traverses through the negative cycle or negative edge, leading to continually decreasing costs each time.
      • If there are multiple shortest paths exist between two nodes, all of them will be found.
      • In disconnected graphs, the algorithm only outputs the shortest paths from the source node to all nodes belonging to the same connected component as the source node.

      Syntax

      • Command: algo(sssp)
      • Parameters:
      Name
      Type
      Spec
      Default
      Optional
      Description
      ids / uuids _id / _uuid / / No ID/UUID of the single source node
      direction string in, out / Yes Direction of the shortest path, ignore the edge direction if not set
      edge_schema_property []@schema?.property Numeric type, must LTE / Yes One or multiple edge properties to be used as edge weights, where the values of multiple properties are summed up; treat the graph as unweighted if not set
      record_path int 0, 1 0 Yes 1 to return the shortest paths, 0 to return the shortest distances
      sssp_type string spfa dijkstra No To run the SPFA, keep it as spfa
      limit int ≥-1 -1 Yes Number of results to return, -1 to return all results
      order string asc, desc / Yes Sort nodes by the shortest distance from the source node

      Examples

      The example graph is as follows:

      File Writeback

      Spec record_path Content Description
      filename 0 _id,totalCost The shortest distance/cost from the source node to each other node
      1 _id--_uuid--_id The shortest path from the source node to each other node, the path is represented by the alternating ID of nodes and UUID of edges that form the path
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        direction: 'out',
        sssp_type: 'spfa'
      }).write({
        file: {
          filename: 'costs'
        }
      })
      

      Results: File costs

      A,0
      B,2
      C,5
      D,5
      E,-3
      F,-4
      G,0
      
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: '@default.value',
        direction: 'out',
        sssp_type: 'spfa',
        record_path: 1
      }).write({
        file: {
          filename: 'paths'
        }
      })
      

      Results: File paths

      A--[101]--B--[104]--C
      A--[101]--B--[105]--D
      A--[101]--B
      A
      A--[101]--B--[103]--F--[107]--E--[109]--G
      A--[101]--B--[103]--F--[107]--E
      A--[101]--B--[103]--F
      

      Direct Return

      Alias Ordinal record_path Type Description Columns
      0 0 []perNode The shortest cost/distance from the source node to each other node _uuid, totalCost
      1 []perPath The shortest path from the source node to each other node, the path is represented by the alternating UUID of nodes and UUID of edges that form the path /
      algo(sssp).params({
        uuids: 1,
        edge_schema_property: 'value',
        sssp_type: 'spfa',
        record_path: 0,
        direction: 'in'
      }) as costs
      return costs
      

      Results: costs

      _uuid totalCost
      1 0
      2 -2
      4 6
      6 4
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        sssp_type: 'spfa',
        direction: 'in',
        record_path: 1
      }) as paths
      return paths
      

      Results: paths

      1--[102]--6--[106]--4
      1--[102]--6
      1
      1--[102]--6--[103]--2

      Stream Return

      Alias Ordinal record_path Type Description Columns
      0 0 []perNode The shortest cost/distance from the source node to each other node _uuid, totalCost
      1 []perPath The shortest path from the source node to each other node, the path is represented by the alternating UUID of nodes and UUID of edges that form the path /
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        sssp_type: 'spfa',
        direction: 'out'
      }).stream() as costs
      where costs.totalCost < 0
      return costs
      

      Results: costs

      _uuid totalCost
      5 -3
      6 -4
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        sssp_type: 'spfa',
        direction: 'out',
        record_path: 1
      }).stream() as p
      where length(p) <> [0,3]
      return p
      

      Results: p

      1--[101]--2--[104]--3
      1--[101]--2--[105]--4
      1--[101]--2
      1--[101]--2--[103]--6
      Please complete the following information to download this book
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写