PGX 21.1.1
Documentation

# Dijkstra Algorithms

Dijkstra's algorithm computes the shortest path between a given source and destination vertex. Besides the classic Dijkstra algorithm, PGX supports a filtered version of Dijkstra's algorithm, which operates on a filtered version of the graph, specified by a PGX filter expression argument.

## Classic Dijkstra Algorithm

##### Categorypath findingAlgorithm IDpgx_builtin_p1a_single_source_single_destination_dijkstraTime ComplexityO(E + V log V) with V = number of vertices, E = number of edgesSpace RequirementO(4 * V) with V = number of verticesJavadocAnalyst#shortestPathDijkstra(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost) Analyst#shortestPathDijkstra(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, VertexProperty> parent, VertexProperty parentEdge)

Dijkstra's algorithm tries to find the shortest path (if there is one) between the given source and destination vertices, while minimizing the distance or cost associated to each edge in the graph.

### Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
root node the source vertex from the graph for the path.
dest node the destination vertex from the graph for the path.
Output Argument Type Comment
parent vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.
Return Value Type Comment
bool true if there is a path connecting source and destination vertices, false otherwise

### Code

```/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;

@GraphAlgorithm
public class Dijkstra {
public boolean dijkstra(PgxGraph g, EdgeProperty<Double> weight, PgxVertex root, PgxVertex dest,
@Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
if (g.getNumVertices() == 0) {
return false;
}

VertexProperty<Boolean> reached = VertexProperty.create();

// sequentially initialize, otherwise compiler flags this algorithm as
//parallel in nature
g.getVertices().forSequential(n -> {
parent.set(n, PgxVertex.NONE);
parentEdge.set(n, PgxEdge.NONE);
reached.set(n, false);
});

//-------------------------------
// look up the vertex
//-------------------------------
PgxMap<PgxVertex, Double> reachable = PgxMap.create();
reachable.set(root, 0d);

//-------------------------------
// look up the vertex
//-------------------------------
boolean found = false;
boolean failed = false;

while (!found && !failed) {
if (reachable.size() == 0) {
failed = true;
} else {
PgxVertex next = reachable.getKeyForMinValue();
if (next == dest) {
found = true;
} else {
reached.set(next, true);
double dist = reachable.get(next);
reachable.remove(next);
next.getNeighbors().filter(v -> !reached.get(v)).forSequential(v -> {
PgxEdge e = v.edge();
if (!reachable.containsKey(v)) {
reachable.set(v, dist + weight.get(e));
parent.set(v, next);
parentEdge.set(v, e);
} else if (reachable.get(v) > dist + weight.get(e)) {
reachable.set(v, dist + weight.get(e));
parent.set(v, next);
parentEdge.set(v, e);
}
});
}
}
}

// return false if not reachable
return !failed;
}
}
```
```/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/

procedure dijkstra(graph G, edgeProp<double> weight, node root, node dest;
vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

if (G.numNodes() == 0) {
return false;
}

vertexProp<bool> reached;

// sequentially initialize, otherwise compiler flags this algorithm as
//parallel in nature
for (n: G.nodes) {
n.parent = NIL;
n.parent_edge = NIL;
n.reached = false;
}

//-------------------------------
// look up the vertex
//-------------------------------
map<node, double> reachable;
reachable[root] = 0.0;            // Add root to reachable set

//-------------------------------
// look up the vertex
//-------------------------------
bool found = false;
bool failed = false;
while (!found && !failed) {

if (reachable.size() == 0) {
failed = true;
}
else {
node next = reachable.getMinKey();
if (next == dest)  {
found = true;
}
else {
next.reached = true;
double dist = reachable[next];
reachable.remove(next);
for (v: next.nbrs) (!v.reached) {

edge e = v.edge();
if (!reachable.hasKey(v)) {
reachable[v] = dist + e.weight;
v.parent = next;
v.parent_edge = e;
}
else if (reachable[v] > dist + e.weight) {
reachable[v] = dist + e.weight;
v.parent = next;
v.parent_edge = e;
}
}
}
}
}
// return false if not reachable
return !failed;
}
```

## Filtered Dijkstra Algorithm

##### Categorypath findingAlgorithm IDpgx_builtin_p1b_single_source_single_destination_filtered_dijkstraTime ComplexityO(E + V log V) with V = number of vertices, E = number of edgesSpace RequirementO(4 * V) with V = number of verticesJavadocAnalyst#shortestPathFilteredDijkstra(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, GraphFilter filterExpr) Analyst#shortestPathFilteredDijkstra(PgxGraph graph, PgxVertex src, PgxVertex dst, EdgeProperty cost, GraphFilter filterExpr, VertexProperty> parent, VertexProperty parentEdge)

This variant of the Dijkstra's algorithm tries to find the shortest path while also taking into account a filter expression, which will add restrictions over the potential edges when looking for the shortest path between the source and destination vertices.

### Signature

Input Argument Type Comment
G graph
weight edgeProp edge property holding the (positive) weight of each edge in the graph.
root node the source vertex from the graph for the path.
dest node the destination vertex from the graph for the path.
filter edgeFilter filter expression with conditions to be satisfied by the shortest path. If the expression is targeted to edges, it will be evaluated straight away. If the expression targets vertices, then it will be automatically translated into an equivalent edge expression by using the sources and/or the destinations of the edges from the current evaluated vertex, with exception of the source and destination vertices.
Output Argument Type Comment
parent vertexProp vertex property holding the parent vertex of the each vertex in the shortest path.
parent_edge vertexProp vertex property holding the edge ID linking the current vertex in the path with the previous vertex in the path.
Return Value Type Comment
bool true if there is a path connecting source and destination vertices, false otherwise

### Code

```/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
package oracle.pgx.algorithms;

import oracle.pgx.algorithm.EdgeProperty;
import oracle.pgx.algorithm.PgxEdge;
import oracle.pgx.algorithm.PgxGraph;
import oracle.pgx.algorithm.PgxMap;
import oracle.pgx.algorithm.PgxVertex;
import oracle.pgx.algorithm.VertexProperty;
import oracle.pgx.algorithm.annotations.GraphAlgorithm;
import oracle.pgx.algorithm.annotations.Out;
import oracle.pgx.algorithm.filter.EdgeFilter;

@GraphAlgorithm
public class DijkstraFiltered {
public boolean dijkstra(PgxGraph g, EdgeProperty<Double> weight, PgxVertex root, PgxVertex dest, EdgeFilter filter,
@Out VertexProperty<PgxVertex> parent, @Out VertexProperty<PgxEdge> parentEdge) {
if (g.getNumVertices() == 0) {
return false;
}

VertexProperty<Boolean> reached = VertexProperty.create();

// sequentially initialize, otherwise compiler flags this algorithm as
//parallel in nature
g.getVertices().forSequential(n -> {
parent.set(n, PgxVertex.NONE);
parentEdge.set(n, PgxEdge.NONE);
reached.set(n, false);
});

//-------------------------------
// look up the vertex
//-------------------------------
PgxMap<PgxVertex, Double> reachable = PgxMap.create();
reachable.set(root, 0d);

//-------------------------------
// look up the vertex
//-------------------------------
boolean found = false;
boolean failed = false;

while (!found && !failed) {
if (reachable.size() == 0) {
failed = true;
} else {
PgxVertex next = reachable.getKeyForMinValue();
if (next == dest) {
found = true;
} else {
reached.set(next, true);
double dist = reachable.get(next);
reachable.remove(next);

next.getNeighbors().filter(v -> !reached.get(v)).forSequential(v -> {
PgxEdge e = v.edge();

if (filter.evaluate(e)) {
if (!reachable.containsKey(v)) {
reachable.set(v, dist + weight.get(e));
parent.set(v, next);
parentEdge.set(v, e);
} else if (reachable.get(v) > dist + weight.get(e)) {
reachable.set(v, dist + weight.get(e));
parent.set(v, next);
parentEdge.set(v, e);
}
}
});
}
}
}

// return false if not reachable
return !failed;
}
}
```
```/*
* Copyright (C) 2013 - 2020 Oracle and/or its affiliates. All rights reserved.
*/
procedure dijkstra_filter(graph G, edgeProp<double> weight, node root, node dest, edgeFilter filter;
vertexProp<node> parent, vertexProp<edge> parent_edge) : bool {

if (G.numNodes() == 0) {
return false;
}

vertexProp<bool> reached;
// sequentially initialize, otherwise compiler flags this algorithm as
// parallel in nature
for (n: G.nodes) {
n.parent = NIL;
n.parent_edge = NIL;
n.reached = false;
}

map<node, double> reachable;
reachable[root] = 0.0;

bool found = false;
bool failed = false;

while (!found && !failed) {
if (reachable.size() == 0) {
failed = true;
} else {
node next = reachable.getMinKey();
if (next == dest)  {
found = true;
} else {
next.reached = true;
double dist = reachable[next];
reachable.remove(next);

for (v: next.nbrs) (!v.reached) {
edge e = v.edge();

if (filter.evaluate(e)) {
if (!reachable.hasKey(v)) {
reachable[v] = dist + e.weight;
v.parent = next;
v.parent_edge = e;
} else if (reachable[v] > dist + e.weight) {
reachable[v] = dist + e.weight;
v.parent = next;
v.parent_edge = e;
}
}
}
}
}
}
// return false if not reachable
return !failed;
}
```