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.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

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

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

v4.5
Search
    English
    v4.5

      Dijkstra's Single-Source Shortest Path

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

      Overview

      The single-source shortest path (SSSP) problem is that of computing, for each node that is reachable from the source node, the shortest path with the minimum total edge weights among all possible paths; or in the case of unweighted graphs, the shortest path with the minimum number of edges. The cost (or distance) of the shortest path is the total edge weights or the number of edges.

      The original Dijkstra's algorithm was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956 to find the shortest path between two given nodes. Single-source shortest path is a common variant, facilitating effective path planning and network analysis.

      Concepts

      Dijkstra's Single-Source Shortest Path

      Below is the basic implementation of the Dijkstra's Single-Source Shortest Path algorithm, along with an example to compute the weighted shortest paths in an undirected graph starting from the source node b:

      1. Create a priority queue to store nodes and their corresponding distances from the source node. Initialize the distance of the source node as 0 and the distances of all other nodes as infinity. All node are marked as unvisited.

      2. Extract the node with the minimum distance from the queue and mark it as visited, relax all its unvisited neighbors.

      Visit node b:
      dist(a) = min(0+2,∞) = 2, dist(c) = min(0+1,∞) = 1

      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 dist(v) = dist(u) + w(u,v), where w(u,v) is the weight of the edge (u,v). This update is performed only if the current dist(v) is greater than dist(u) + w(u,v).

      Once a node has been marked as visited, its shortest path has been fixed and its distance will not change during the rest of the algorithm. The algorithm only updates the distances of node that have not been visited yet.

      3. Repeat step 2 until all nodes are visited.

      Visit node c:
      dist(d) = min(1+3, ∞) = 4, dist(e) = min(1+4, ∞) = 5, dist(g) = min(1+2, ∞) = 3

      Visit node a:
      dist(d) = min(2+4, 4) = 4

      Visit node g:
      dist(f) = min(3+5, ∞) = 8

      Visit node d:
      No neighbor can be relaxed

      Visit node e:
      dist(f) = min(5+8, 8) = 8

      Visit node f:
      No neighbor can be relaxed
      The algorithm ends here as all nodes are visited

      Considerations

      • The Dijkstra's algorithm is only applicable to graphs with non-negative edge weights. If negative weights are present, the Dijkstra's algorithm might produce false results. In this case, a different algorithm like the SPFA should be used.
      • 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 dijkstra dijkstra Yes To run the Dijkstra's SSSP algorithm, keep it as dijkstra
      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'
      }).write({
        file: {
          filename: 'costs'
        }
      })
      

      Results: File costs

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

      Results: File paths

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

      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: '@default.value',
        sssp_type: 'dijkstra',
        record_path: 0,
        order: 'desc'
      }) as costs
      return costs
      

      Results: costs

      _uuid totalCost
      7 8
      5 5
      4 5
      3 5
      6 4
      2 2
      1 0
      algo(sssp).params({
        ids: 'A',
        edge_schema_property: '@default.value',
        direction: 'out',
        record_path: 1, 
        order: 'asc'
      }) as paths
      return paths
      

      Results: paths

      1
      1--[101]--2
      1--[102]--6
      1--[102]--6--[107]--5
      1--[101]--2--[105]--4
      1--[101]--2--[104]--3
      1--[102]--6--[107]--5--[109]--7

      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({
        uuids: 1,
        edge_schema_property: '@default.value',
        sssp_type: 'dijkstra'
      }).stream() as costs
      where costs.totalCost <> [0,5]
      return costs
      

      Results: costs

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

      Results: p

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