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.

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.

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.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().edge_property(@default, "value", int32)
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"B", value:2}, {_from:"A", _to:"F", value:4}, {_from:"B", _to:"F", value:6}, {_from:"B", _to:"C", value:3}, {_from:"B", _to:"D", value:3}, {_from:"D", _to:"F", value:2}, {_from:"F", _to:"E", value:1}, {_from:"D", _to:"E", value:2}, {_from:"E", _to:"G", value:3}])

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as hdc_sssp:

CALL hdc.graph.create("hdc-server-1", "hdc_sssp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_sssp", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: sssp

File Writeback

CALL algo.sssp.write("hdc_sssp", {
  params: {
    ids: "A",
    edge_schema_property: "@default.value",
    impl_type: "dijkstra",
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "costs"
    }
  }
})

algo(sssp).params({
  project: "hdc_sssp",
  ids: "A",
  edge_schema_property: "@default.value",
  impl_type: "dijkstra",
  return_id_uuid: "id"
}).write({
  file: {
      filename: "costs"
  }
})

Result:

_id,totalCost
D,5
F,4
B,2
E,5
C,5
G,8

CALL algo.sssp.write("hdc_sssp", {
  params: {
    ids: "A",
    edge_schema_property: "@default.value",
    impl_type: "dijkstra",
    record_path: 1,
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "paths"
    }
  }
})

algo(sssp).params({
  project: "hdc_sssp",
  ids: "A",
  edge_schema_property: "@default.value",
  impl_type: "dijkstra",
  record_path: 1,
  return_id_uuid: "id"
}).write({
  file: {
      filename: "paths"
  }
})

Result:

totalCost,_ids
8,A--[102]--F--[107]--E--[109]--G
5,A--[101]--B--[105]--D
5,A--[102]--F--[107]--E
5,A--[101]--B--[104]--C
4,A--[102]--F
2,A--[101]--B

Full Return

CALL algo.sssp("hdc_sssp", {
  params: {
    ids: 'A',
    edge_schema_property: 'value',
    impl_type: 'dijkstra',
    record_path: 0,
    return_id_uuid: 'id',
    order: 'desc'
  },
  return_params: {}
}) YIELD r
RETURN r

exec{
  algo(sssp).params({
    ids: 'A',
    edge_schema_property: 'value',
    impl_type: 'dijkstra',
    record_path: 0,
    return_id_uuid: 'id',
    order: 'desc'
  }) as r
  return r
} on hdc_sssp

Result:

Stream Return

CALL algo.sssp("hdc_sssp", {
  params: {
    ids: 'A',
    edge_schema_property: '@default.value',
    impl_type: 'dijkstra',
    record_path: 1,
    return_id_uuid: 'id'
  },
  return_params: {
    stream: {}
  }
}) YIELD r
RETURN r

exec{
  algo(sssp).params({
    ids: 'A',
    edge_schema_property: '@default.value',
    impl_type: 'dijkstra',
    record_path: 1,
    return_id_uuid: 'id'
  }).stream() as r
  return r
} on hdc_sssp

Result: