Dijkstra Shortest Path¶

Algorithm introduction¶

Dijkstra shortest path computes the minimum path cost from a source node to all reachable nodes on non-negative weighted graphs.

Compute the classic Dijkstra shortest path in a directed weighted graph whose node primary key is id and edge weight property is weight. Edge weights must be non-negative.

For more information, see Dijkstra Shortest Path.

Data model¶

To implement the Dijkstra Shortest Path algorithm in GQL, the following data model is used to create a graph type:

Entities are represented by nodes of type Node, with properties id and rating.
Relationships are represented by edges of type Link, with property weight.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation ¶

To compute Dijkstra Shortest Path results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

source_id: INT64. ID of the source node.
target_id: INT64. ID of the target node.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
`search_done`	Primitive value variable	Flag indicating Dijkstra's search has terminated.
`has_path`	Primitive value variable	Whether a path from source to target was found.
`inf`	Primitive value variable	Infinity sentinel for uninitialized distances.
`current_id`	Primitive value variable	ID of the node currently being settled.
`current_dist`	Primitive value variable	Distance from source to the currently settled node.
`final_cost`	Primitive value variable	Total shortest-path cost from source to target.
`walk_id`	Primitive value variable	Node ID used during reverse path reconstruction.
`reverse_step`	Primitive value variable	Step counter during reverse path reconstruction.
`path_len`	Primitive value variable	Total path length (number of hops).
`best_open`	Global SumAgg aggregator value variable	Min-heap entry selecting the next node to settle.
`pick_state`	Global SumAgg aggregator value variable	State of the node currently being settled.
`back_state`	Global SumAgg aggregator value variable	State used during path reconstruction.
`dist`	Node-attached SumAgg aggregator value variable	Per-node tentative shortest distance from source.
`parent`	Node-attached SumAgg aggregator value variable	Per-node parent node on the shortest path.
`edge_w`	Node-attached SumAgg aggregator value variable	Per-node incoming edge weight on the shortest path.
`opened`	Node-attached SumAgg aggregator value variable	Per-node flag: node is in the priority queue.
`settled`	Node-attached SumAgg aggregator value variable	Per-node flag: node's distance has been finalized.
`cand`	Node-attached SumAgg aggregator value variable	Per-node best relaxation candidate in the current expansion step.
`path_table`	Table variable	Intermediate table storing reversed path steps.

The following steps outline the logic of the procedure:

Initialize all nodes' dist to infinity; set the source node's dist to 0 and add it to the open set.
Repeatedly settle the open-set node with the smallest dist (best_open); if it is the target, record final_cost and stop.
For each outgoing edge, relax the neighbor's dist; if improved, update dist, parent, edge_w and re-add to the open set.
Reconstruct the shortest path from target to source via parent; return ordered path steps.

Steps¶

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

Create a graph type that matches your data model.

'''
CREATE GRAPH TYPE IF NOT EXISTS dijkstra_shortest_path_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

Download these CSV files and save them with their original names in examples/algorithms/dijkstra_shortest_path/ under your deployment directory:

dijkstra_shortest_path_node.csv: Node data.
dijkstra_shortest_path_edge.csv: Edge data.

Preview the CSV files

dijkstra_shortest_path_node.csv

id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

dijkstra_shortest_path_edge.csv

src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

Create a temporary graph based on the graph type and load the data files into the temporary graph.

CREATE TEMPORARY GRAPH IF NOT EXISTS #dijkstra_shortest_path_graph TYPED dijkstra_shortest_path_graph_type

'''
USE #dijkstra_shortest_path_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/dijkstra_shortest_path/dijkstra_shortest_path_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/dijkstra_shortest_path/dijkstra_shortest_path_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

After the import succeeds, run this query in the console to check the node count:

'''
USE #dijkstra_shortest_path_graph
MATCH (n)
RETURN count(n) AS node_count
'''

The expected node_count is 24. If it differs, check the files and import results before continuing.

2. Create a procedure ¶

Create a procedure to implement the Dijkstra Shortest Path algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE dijkstra_shortest_path(
  source_id INT64,
  target_id INT64
)
RETURNS (step_no INT64, node_id INT64, parent_id INT64, edge_weight DOUBLE, path_cost DOUBLE, total_cost DOUBLE)
COMMENT "Compute the classic Dijkstra shortest path in a directed weighted graph whose vertex primary key is id and edge weight property is weight. Edge weights must be non-negative."
AS {
  VALUE search_done BOOLEAN = false
  VALUE has_path BOOLEAN = false
  VALUE inf DOUBLE = 1000000000000000000.0
  VALUE current_id INT64 = 0
  VALUE current_dist DOUBLE = 0.0
  VALUE final_cost DOUBLE = 0.0
  VALUE walk_id INT64 = 0
  VALUE reverse_step INT64 = 0
  VALUE path_len INT64 = 0

  VALUE best_open TopKAgg<1, dist DOUBLE ASC, node_id INT64 ASC>
  VALUE pick_state TopKAgg<1, dist DOUBLE ASC, node_id INT64 ASC>
  VALUE back_state TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>

  NODE VALUE dist MinAgg<DOUBLE> = 1000000000000000000.0
  NODE VALUE parent MinAgg<INT64> = 0
  NODE VALUE edge_w MinAgg<DOUBLE> = 0.0
  NODE VALUE opened OrAgg = false
  NODE VALUE settled OrAgg = false
  NODE VALUE cand TopKAgg<1, dist DOUBLE ASC, parent_id INT64 ASC, edge_weight DOUBLE ASC>

  TABLE path_table TYPED TABLE {
    rev_step INT64,
    node_id INT64,
    parent_id INT64,
    edge_weight DOUBLE,
    path_cost DOUBLE
  }

  MATCH (n)
  PER NODE (n) {
    SET n.@dist = inf
    SET n.@parent = 0
    SET n.@edge_w = 0.0
    SET n.@opened = false
    SET n.@settled = false
    SET n.@cand.clear()
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@dist = 0.0
    SET s.@parent = source_id
    SET s.@edge_w = 0.0
    SET s.@opened = true
    SET s.@settled = false
  }

  WHILE search_done = false THEN {
    SET @best_open.clear()

    MATCH (n)
    WHERE n.@opened = true AND n.@settled = false
    PER NODE (n) {
      SET @best_open += RECORD{dist: n.@dist, node_id: n.id}
    }

    IF @best_open.size() = 0 THEN {
      SET search_done = true
    }
    ELSE {
      SET current_id = @best_open.min().node_id
      SET @pick_state.clear()

      MATCH (u)
      WHERE u.id = current_id
      PER NODE (u) {
        SET @pick_state += RECORD{dist: u.@dist, node_id: u.id}
        SET u.@opened = false
        SET u.@settled = true
      }

      SET current_dist = @pick_state.min().dist

      IF current_id = target_id THEN {
        SET final_cost = current_dist
        SET has_path = true
        SET search_done = true
      }
      ELSE {
        MATCH (v)
        WHERE v.@settled = false
        PER NODE (v) {
          SET v.@cand.clear()
        }

        MATCH (u)-[e]->(v)
        WHERE u.id = current_id AND v.@settled = false
        PER PATH {
          VALUE tentative DOUBLE = 0.0
          VALUE edge_cost DOUBLE = 0.0

          SET edge_cost = CAST(e.weight AS DOUBLE)
          SET tentative = current_dist + edge_cost

          IF tentative < v.@dist THEN {
            SET v.@cand += RECORD{
              dist: tentative,
              parent_id: current_id,
              edge_weight: edge_cost
            }
          }
        }

        MATCH (v)
        WHERE v.@settled = false AND v.@cand.size() > 0
        PER NODE (v) {
          SET v.@dist = v.@cand.min().dist
          SET v.@parent = v.@cand.min().parent_id
          SET v.@edge_w = v.@cand.min().edge_weight
          SET v.@opened = true
        }
      }
    }
  }

  IF has_path = true THEN {
    SET walk_id = target_id
    SET reverse_step = 0

    WHILE walk_id <> source_id THEN {
      SET @back_state.clear()

      MATCH (n)
      WHERE n.id = walk_id
      PER NODE (n) {
        SET @back_state += RECORD{
          dist: n.@dist,
          parent_id: n.@parent,
          edge_weight: n.@edge_w
        }
      }

      EXPORT
        reverse_step,
        walk_id,
        @back_state.min().parent_id,
        @back_state.min().edge_weight,
        @back_state.min().dist
      INTO path_table

      SET walk_id = @back_state.min().parent_id
      SET reverse_step = reverse_step + 1
    }

    SET @back_state.clear()

    MATCH (n)
    WHERE n.id = source_id
    PER NODE (n) {
      SET @back_state += RECORD{
        dist: n.@dist,
        parent_id: n.@parent,
        edge_weight: n.@edge_w
      }
    }

    EXPORT reverse_step, source_id, @back_state.min().parent_id, 0.0, @back_state.min().dist INTO path_table
    SET path_len = reverse_step
  }

  FOR r IN path_table
  RETURN
    path_len - r.rev_step AS step_no,
    r.node_id AS node_id,
    r.parent_id AS parent_id,
    r.edge_weight AS edge_weight,
    r.path_cost AS path_cost,
    final_cost AS total_cost
  ORDER BY step_no ASC
}
'''

3. Call your procedure ¶

Find a path from node 1 to node 24, returning its nodes, edge weights, and accumulated costs.

USE #dijkstra_shortest_path_graph CALL dijkstra_shortest_path(1, 24) RETURN step_no, node_id, parent_id, edge_weight, path_cost, total_cost

Returns:

Expand to view results

+---------+---------+-----------+-------------+-----------+------------+
| step_no | node_id | parent_id | edge_weight | path_cost | total_cost |
+---------+---------+-----------+-------------+-----------+------------+
| 0       | 1       | 1         | 0.0         | 0.0       | 23.0       |
| 1       | 2       | 1         | 4.0         | 4.0       | 23.0       |
| 2       | 6       | 2         | 2.0         | 6.0       | 23.0       |
| 3       | 8       | 6         | 1.0         | 7.0       | 23.0       |
| 4       | 9       | 8         | 3.0         | 10.0      | 23.0       |
| 5       | 13      | 9         | 2.0         | 12.0      | 23.0       |
| 6       | 15      | 13        | 2.0         | 14.0      | 23.0       |
| 7       | 19      | 15        | 3.0         | 17.0      | 23.0       |
| 8       | 21      | 19        | 1.0         | 18.0      | 23.0       |
| 9       | 23      | 21        | 4.0         | 22.0      | 23.0       |
| 10      | 24      | 23        | 1.0         | 23.0      | 23.0       |
+---------+---------+-----------+-------------+-----------+------------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.

Dijkstra Shortest Path¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶