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.
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.
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 |
/* * 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; }
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.
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 |
/* * 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; }