Geometry Nodes: Shortest Paths nodes

This adds three new nodes:
* `Shortest Edge Paths`: Actually finds the shortest paths.
* `Edge Paths to Curves`: Converts the paths to separate curves.
  This may generate a quadratic amount of data, making it slow
  for large meshes.
* `Edge Paths to Selection`: Generates an edge selection that
  contains all edges that are part of a path. This can be used
  with the Separate Geometry node to only keep the edges that
  are part of a path. For large meshes, this approach can be
  much faster than the `Edge Paths to Curves` node, because
  less data is created.

Differential Revision: https://developer.blender.org/D15274

10 files changed, 524 insertions, 4 deletions

diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index ea43fba1a85..c340359f48b 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -1506,6 +1506,9 @@ struct TexResult;
 #define GEO_NODE_UV_UNWRAP 1165
 #define GEO_NODE_UV_PACK_ISLANDS 1166
 #define GEO_NODE_DEFORM_CURVES_ON_SURFACE 1167
+#define GEO_NODE_INPUT_SHORTEST_EDGE_PATHS 1168
+#define GEO_NODE_EDGE_PATHS_TO_CURVES 1169
+#define GEO_NODE_EDGE_PATHS_TO_SELECTION 1170
 
 /** \} */
 
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index c6f140b9260..bcdc06b541e 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -4754,6 +4754,8 @@ static void registerGeometryNodes()
   register_node_type_geo_duplicate_elements();
   register_node_type_geo_distribute_points_on_faces();
   register_node_type_geo_dual_mesh();
+  register_node_type_geo_edge_paths_to_curves();
+  register_node_type_geo_edge_paths_to_selection();
   register_node_type_geo_edge_split();
   register_node_type_geo_extrude_mesh();
   register_node_type_geo_field_at_index();
@@ -4783,6 +4785,7 @@ static void registerGeometryNodes()
   register_node_type_geo_input_radius();
   register_node_type_geo_input_scene_time();
   register_node_type_geo_input_shade_smooth();
+  register_node_type_geo_input_shortest_edge_paths();
   register_node_type_geo_input_spline_cyclic();
   register_node_type_geo_input_spline_length();
   register_node_type_geo_input_spline_resolution();
diff --git a/source/blender/geometry/GEO_mesh_to_curve.hh b/source/blender/geometry/GEO_mesh_to_curve.hh
index f619aaff217..b0f24853dbc 100644
--- a/source/blender/geometry/GEO_mesh_to_curve.hh
+++ b/source/blender/geometry/GEO_mesh_to_curve.hh
@@ -21,4 +21,9 @@ namespace blender::geometry {
  */
 bke::CurvesGeometry mesh_to_curve_convert(const Mesh &mesh, const IndexMask selection);
 
+bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
+                                                   Span<int> vert_indices,
+                                                   Span<int> curve_offsets,
+                                                   IndexRange cyclic_curves);
+
 }  // namespace blender::geometry
diff --git a/source/blender/geometry/intern/mesh_to_curve_convert.cc b/source/blender/geometry/intern/mesh_to_curve_convert.cc
index fdacb174462..350dfe73d57 100644
--- a/source/blender/geometry/intern/mesh_to_curve_convert.cc
+++ b/source/blender/geometry/intern/mesh_to_curve_convert.cc
@@ -30,10 +30,10 @@ static void copy_with_map(const VArray<T> &src, Span<int> map, MutableSpan<T> ds
   });
 }
 
-static bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
-                                                          const Span<int> vert_indices,
-                                                          const Span<int> curve_offsets,
-                                                          const IndexRange cyclic_curves)
+bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh,
+                                                   const Span<int> vert_indices,
+                                                   const Span<int> curve_offsets,
+                                                   const IndexRange cyclic_curves)
 {
   bke::CurvesGeometry curves(vert_indices.size(), curve_offsets.size());
   curves.offsets_for_write().drop_back(1).copy_from(curve_offsets);
diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h
index 86c276fbd6f..7dcbfb50a2c 100644
--- a/source/blender/nodes/NOD_geometry.h
+++ b/source/blender/nodes/NOD_geometry.h
@@ -52,6 +52,8 @@ void register_node_type_geo_delete_geometry(void);
 void register_node_type_geo_duplicate_elements(void);
 void register_node_type_geo_distribute_points_on_faces(void);
 void register_node_type_geo_dual_mesh(void);
+void register_node_type_geo_edge_paths_to_curves(void);
+void register_node_type_geo_edge_paths_to_selection(void);
 void register_node_type_geo_edge_split(void);
 void register_node_type_geo_extrude_mesh(void);
 void register_node_type_geo_field_at_index(void);
@@ -81,6 +83,7 @@ void register_node_type_geo_input_position(void);
 void register_node_type_geo_input_radius(void);
 void register_node_type_geo_input_scene_time(void);
 void register_node_type_geo_input_shade_smooth(void);
+void register_node_type_geo_input_shortest_edge_paths(void);
 void register_node_type_geo_input_spline_cyclic(void);
 void register_node_type_geo_input_spline_length(void);
 void register_node_type_geo_input_spline_resolution(void);
diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h
index db0204c5426..10bb336fc1b 100644
--- a/source/blender/nodes/NOD_static_types.h
+++ b/source/blender/nodes/NOD_static_types.h
@@ -307,6 +307,8 @@ DefNode(GeometryNode, GEO_NODE_DUPLICATE_ELEMENTS, def_geo_duplicate_elements, "
 DefNode(GeometryNode, GEO_NODE_DISTRIBUTE_POINTS_ON_FACES, def_geo_distribute_points_on_faces, "DISTRIBUTE_POINTS_ON_FACES", DistributePointsOnFaces, "Distribute Points on Faces", "Generate points spread out on the surface of a mesh")
 DefNode(GeometryNode, GEO_NODE_ACCUMULATE_FIELD, def_geo_accumulate_field, "ACCUMULATE_FIELD", AccumulateField, "Accumulate Field", "Add the values of an evaluated field together and output the running total for each element")
 DefNode(GeometryNode, GEO_NODE_DUAL_MESH, 0, "DUAL_MESH", DualMesh, "Dual Mesh", "Convert Faces into vertices and vertices into faces")
+DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_CURVES, 0, "EDGE_PATHS_TO_CURVES", EdgePathsToCurves, "Edge Paths to Curves", "")
+DefNode(GeometryNode, GEO_NODE_EDGE_PATHS_TO_SELECTION, 0, "EDGE_PATHS_TO_SELECTION", EdgePathsToSelection, "Edge Paths to Selection", "")
 DefNode(GeometryNode, GEO_NODE_EXTRUDE_MESH, def_geo_extrude_mesh, "EXTRUDE_MESH", ExtrudeMesh, "Extrude Mesh", "Generate new vertices, edges, or faces from selected elements and move them based on an offset while keeping them connected by their boundary")
 DefNode(GeometryNode, GEO_NODE_FIELD_AT_INDEX, def_geo_field_at_index, "FIELD_AT_INDEX", FieldAtIndex, "Field at Index", "Retrieve data of other elements in the context's geometry")
 DefNode(GeometryNode, GEO_NODE_FIELD_ON_DOMAIN, def_geo_field_on_domain, "FIELD_ON_DOMAIN", FieldOnDomain, "Field on Domain", "Retrieve values from a field on a different domain besides the domain from the context")
@@ -337,6 +339,7 @@ DefNode(GeometryNode, GEO_NODE_INPUT_POSITION, 0, "POSITION", InputPosition, "Po
 DefNode(GeometryNode, GEO_NODE_INPUT_RADIUS, 0, "INPUT_RADIUS", InputRadius, "Radius", "Retrieve the radius at each point on curve or point cloud geometry")
 DefNode(GeometryNode, GEO_NODE_INPUT_SCENE_TIME, 0, "INPUT_SCENE_TIME", InputSceneTime, "Scene Time", "Retrieve the current time in the scene's animation in units of seconds or frames")
 DefNode(GeometryNode, GEO_NODE_INPUT_SHADE_SMOOTH, 0, "INPUT_SHADE_SMOOTH", InputShadeSmooth, "Is Shade Smooth", "Retrieve whether each face is marked for smooth shading")
+DefNode(GeometryNode, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS, 0, "SHORTEST_EDGE_PATHS", InputShortestEdgePaths, "Shortest Edge Paths", "")
 DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_CYCLIC, 0, "INPUT_SPLINE_CYCLIC",InputSplineCyclic, "Is Spline Cyclic", "Retrieve whether each spline endpoint connects to the beginning")
 DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_LENGTH, 0, "SPLINE_LENGTH", SplineLength, "Spline Length", "Retrieve the total length of each spline, as a distance or as a number of points")
 DefNode(GeometryNode, GEO_NODE_INPUT_SPLINE_RESOLUTION, 0, "INPUT_SPLINE_RESOLUTION", InputSplineResolution, "Spline Resolution", "Retrieve the number of evaluated points that will be generated for every control point on curves")
diff --git a/source/blender/nodes/geometry/CMakeLists.txt b/source/blender/nodes/geometry/CMakeLists.txt
index d87f0312958..97353000b8a 100644
--- a/source/blender/nodes/geometry/CMakeLists.txt
+++ b/source/blender/nodes/geometry/CMakeLists.txt
@@ -62,6 +62,8 @@ set(SRC
   nodes/node_geo_distribute_points_on_faces.cc
   nodes/node_geo_dual_mesh.cc
   nodes/node_geo_duplicate_elements.cc
+  nodes/node_geo_edge_paths_to_curves.cc
+  nodes/node_geo_edge_paths_to_selection.cc
   nodes/node_geo_edge_split.cc
   nodes/node_geo_extrude_mesh.cc
   nodes/node_geo_field_at_index.cc
@@ -91,6 +93,7 @@ set(SRC
   nodes/node_geo_input_radius.cc
   nodes/node_geo_input_scene_time.cc
   nodes/node_geo_input_shade_smooth.cc
+  nodes/node_geo_input_shortest_edge_paths.cc
   nodes/node_geo_input_spline_cyclic.cc
   nodes/node_geo_input_spline_length.cc
   nodes/node_geo_input_spline_resolution.cc
diff --git a/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc
new file mode 100644
index 00000000000..89abfa0aa88
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_curves.cc
@@ -0,0 +1,113 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BKE_curves.hh"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "GEO_mesh_to_curve.hh"
+
+#include "node_geometry_util.hh"
+
+namespace blender::nodes::node_geo_edge_paths_to_curves_cc {
+
+static void node_declare(NodeDeclarationBuilder &b)
+{
+  b.add_input<decl::Geometry>(N_("Mesh")).supported_type(GEO_COMPONENT_TYPE_MESH);
+  b.add_input<decl::Bool>(N_("Start Vertices")).default_value(true).hide_value().supports_field();
+  b.add_input<decl::Int>(N_("Next Vertex Index")).default_value(-1).hide_value().supports_field();
+  b.add_output<decl::Geometry>(N_("Curves"));
+}
+
+static Curves *edge_paths_to_curves_convert(const Mesh &mesh,
+                                            const IndexMask start_verts_mask,
+                                            const Span<int> next_indices)
+{
+  const Span<MVert> mvert{mesh.mvert, mesh.totvert};
+  Vector<int> vert_indices;
+  Vector<int> curve_offsets;
+  Array<bool> visited(mesh.totvert, false);
+  for (const int first_vert : start_verts_mask) {
+    const int second_vert = next_indices[first_vert];
+    if (first_vert == second_vert) {
+      continue;
+    }
+    if (second_vert < 0 || second_vert >= mesh.totvert) {
+      continue;
+    }
+
+    curve_offsets.append(vert_indices.size());
+
+    /* Iterate through path defined by #next_indices. */
+    int current_vert = first_vert;
+    while (!visited[current_vert]) {
+      visited[current_vert] = true;
+      vert_indices.append(current_vert);
+      const int next_vert = next_indices[current_vert];
+      if (next_vert < 0 || next_vert >= mesh.totvert) {
+        break;
+      }
+      current_vert = next_vert;
+    }
+
+    /* Reset visited status. */
+    const int points_in_curve_num = vert_indices.size() - curve_offsets.last();
+    for (const int vert_in_curve : vert_indices.as_span().take_back(points_in_curve_num)) {
+      visited[vert_in_curve] = false;
+    }
+  }
+
+  if (vert_indices.is_empty()) {
+    return nullptr;
+  }
+  Curves *curves_id = bke::curves_new_nomain(
+      geometry::create_curve_from_vert_indices(mesh, vert_indices, curve_offsets, IndexRange(0)));
+  return curves_id;
+}
+
+static void node_geo_exec(GeoNodeExecParams params)
+{
+  GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh");
+
+  geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) {
+    if (!geometry_set.has_mesh()) {
+      geometry_set.keep_only({GEO_COMPONENT_TYPE_INSTANCES});
+      return;
+    }
+
+    const MeshComponent &component = *geometry_set.get_component_for_read<MeshComponent>();
+    GeometryComponentFieldContext context{component, ATTR_DOMAIN_POINT};
+    fn::FieldEvaluator evaluator{context, component.attribute_domain_size(ATTR_DOMAIN_POINT)};
+    evaluator.add(params.get_input<Field<int>>("Next Vertex Index"));
+    evaluator.add(params.get_input<Field<bool>>("Start Vertices"));
+    evaluator.evaluate();
+    const VArraySpan<int> next_vert = evaluator.get_evaluated<int>(0);
+    IndexMask start_verts = evaluator.get_evaluated_as_mask(1);
+
+    if (start_verts.is_empty()) {
+      geometry_set.keep_only({GEO_COMPONENT_TYPE_INSTANCES});
+      return;
+    }
+
+    const Mesh &mesh = *component.get_for_read();
+    geometry_set.replace_curves(edge_paths_to_curves_convert(mesh, start_verts, next_vert));
+    geometry_set.keep_only({GEO_COMPONENT_TYPE_CURVE, GEO_COMPONENT_TYPE_INSTANCES});
+  });
+
+  params.set_output("Curves", std::move(geometry_set));
+}
+
+}  // namespace blender::nodes::node_geo_edge_paths_to_curves_cc
+
+void register_node_type_geo_edge_paths_to_curves()
+{
+  namespace file_ns = blender::nodes::node_geo_edge_paths_to_curves_cc;
+
+  static bNodeType ntype;
+
+  geo_node_type_base(
+      &ntype, GEO_NODE_EDGE_PATHS_TO_CURVES, "Edge Paths to Curves", NODE_CLASS_GEOMETRY);
+  ntype.declare = file_ns::node_declare;
+  ntype.geometry_node_execute = file_ns::node_geo_exec;
+  nodeRegisterType(&ntype);
+}
diff --git a/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc
new file mode 100644
index 00000000000..efdf0911ec9
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/node_geo_edge_paths_to_selection.cc
@@ -0,0 +1,140 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "BKE_attribute_math.hh"
+#include "BKE_mesh.h"
+
+#include "BLI_map.hh"
+#include "BLI_set.hh"
+#include "BLI_task.hh"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "node_geometry_util.hh"
+
+#include <set>
+
+namespace blender::nodes::node_geo_edge_paths_to_selection_cc {
+
+static void node_declare(NodeDeclarationBuilder &b)
+{
+  b.add_input<decl::Bool>(N_("Start Vertices")).default_value(true).hide_value().supports_field();
+  b.add_input<decl::Int>(N_("Next Vertex Index")).default_value(-1).hide_value().supports_field();
+  b.add_output<decl::Bool>(N_("Selection")).field_source();
+}
+
+static void edge_paths_to_selection(const Mesh &src_mesh,
+                                    const IndexMask start_selection,
+                                    const Span<int> next_indices,
+                                    MutableSpan<bool> r_selection)
+{
+  Array<bool> selection(src_mesh.totvert, false);
+
+  for (const int start_vert : start_selection) {
+    selection[start_vert] = true;
+  }
+
+  for (const int start_i : start_selection) {
+    int iter = start_i;
+    while (iter != next_indices[iter] && !selection[next_indices[iter]]) {
+      if (next_indices[iter] < 0 || next_indices[iter] >= src_mesh.totvert) {
+        break;
+      }
+      selection[next_indices[iter]] = true;
+      iter = next_indices[iter];
+    }
+  }
+
+  for (const int i : IndexRange(src_mesh.totedge)) {
+    const MEdge &edge = src_mesh.medge[i];
+    if ((selection[edge.v1] && selection[edge.v2]) &&
+        (edge.v1 == next_indices[edge.v2] || edge.v2 == next_indices[edge.v1])) {
+      r_selection[i] = true;
+    }
+  }
+}
+
+class PathToEdgeSelectionFieldInput final : public GeometryFieldInput {
+ private:
+  Field<bool> start_vertices_;
+  Field<int> next_vertex_;
+
+ public:
+  PathToEdgeSelectionFieldInput(Field<bool> start_vertices, Field<int> next_vertex)
+      : GeometryFieldInput(CPPType::get<bool>(), "Edge Selection"),
+        start_vertices_(start_vertices),
+        next_vertex_(next_vertex)
+  {
+    category_ = Category::Generated;
+  }
+
+  GVArray get_varray_for_context(const GeometryComponent &component,
+                                 const eAttrDomain domain,
+                                 [[maybe_unused]] IndexMask mask) const final
+  {
+    if (component.type() != GEO_COMPONENT_TYPE_MESH) {
+      return {};
+    }
+
+    const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component);
+    const Mesh *mesh = mesh_component.get_for_read();
+    if (mesh == nullptr) {
+      return {};
+    }
+
+    GeometryComponentFieldContext context{mesh_component, ATTR_DOMAIN_POINT};
+    fn::FieldEvaluator evaluator{context, mesh_component.attribute_domain_size(ATTR_DOMAIN_POINT)};
+    evaluator.add(next_vertex_);
+    evaluator.add(start_vertices_);
+    evaluator.evaluate();
+    const VArraySpan<int> next_vert = evaluator.get_evaluated<int>(0);
+    const IndexMask start_verts = evaluator.get_evaluated_as_mask(1);
+
+    if (start_verts.is_empty()) {
+      return {};
+    }
+
+    Array<bool> selection(mesh->totedge, false);
+    MutableSpan<bool> selection_span = selection.as_mutable_span();
+
+    edge_paths_to_selection(*mesh, start_verts, next_vert, selection_span);
+
+    return mesh_component.attributes()->adapt_domain<bool>(
+        VArray<bool>::ForContainer(std::move(selection)), ATTR_DOMAIN_EDGE, domain);
+  }
+
+  uint64_t hash() const override
+  {
+    return get_default_hash_2(start_vertices_, next_vertex_);
+  }
+
+  bool is_equal_to(const fn::FieldNode &other) const override
+  {
+    return dynamic_cast<const PathToEdgeSelectionFieldInput *>(&other) != nullptr;
+  }
+};
+
+static void node_geo_exec(GeoNodeExecParams params)
+{
+  Field<bool> start_vertices = params.extract_input<Field<bool>>("Start Vertices");
+  Field<int> next_vertex = params.extract_input<Field<int>>("Next Vertex Index");
+  Field<bool> selection_field{
+      std::make_shared<PathToEdgeSelectionFieldInput>(start_vertices, next_vertex)};
+  params.set_output("Selection", std::move(selection_field));
+}
+
+}  // namespace blender::nodes::node_geo_edge_paths_to_selection_cc
+
+void register_node_type_geo_edge_paths_to_selection()
+{
+  namespace file_ns = blender::nodes::node_geo_edge_paths_to_selection_cc;
+
+  static bNodeType ntype;
+
+  geo_node_type_base(
+      &ntype, GEO_NODE_EDGE_PATHS_TO_SELECTION, "Edge Paths to Selection", NODE_CLASS_INPUT);
+  ntype.declare = file_ns::node_declare;
+  node_type_size(&ntype, 150, 100, 300);
+  ntype.geometry_node_execute = file_ns::node_geo_exec;
+  nodeRegisterType(&ntype);
+}
diff --git a/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc b/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc
new file mode 100644
index 00000000000..89abaca3c66
--- /dev/null
+++ b/source/blender/nodes/geometry/nodes/node_geo_input_shortest_edge_paths.cc
@@ -0,0 +1,247 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include <queue>
+
+#include "BKE_curves.hh"
+
+#include "BLI_map.hh"
+#include "BLI_math_vec_types.hh"
+#include "BLI_set.hh"
+
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "node_geometry_util.hh"
+
+namespace blender::nodes::node_geo_input_shortest_edge_paths_cc {
+
+static void node_declare(NodeDeclarationBuilder &b)
+{
+  b.add_input<decl::Bool>(N_("End Vertex")).default_value(false).hide_value().supports_field();
+  b.add_input<decl::Float>(N_("Edge Cost")).default_value(1.0f).hide_value().supports_field();
+  b.add_output<decl::Int>(N_("Next Vertex Index")).field_source();
+  b.add_output<decl::Float>(N_("Total Cost")).field_source();
+}
+
+typedef std::pair<float, int> VertPriority;
+
+struct EdgeVertMap {
+  Array<Vector<int>> edges_by_vertex_map;
+
+  EdgeVertMap(const Mesh *mesh)
+  {
+    const Span<MEdge> edges{mesh->medge, mesh->totedge};
+    edges_by_vertex_map.reinitialize(mesh->totvert);
+    for (const int edge_i : edges.index_range()) {
+      const MEdge &edge = edges[edge_i];
+      edges_by_vertex_map[edge.v1].append(edge_i);
+      edges_by_vertex_map[edge.v2].append(edge_i);
+    }
+  }
+};
+
+static void shortest_paths(const Mesh *mesh,
+                           EdgeVertMap &maps,
+                           const IndexMask end_selection,
+                           const VArray<float> &input_cost,
+                           MutableSpan<int> r_next_index,
+                           MutableSpan<float> r_cost)
+{
+  const Span<MVert> verts{mesh->mvert, mesh->totvert};
+  const Span<MEdge> edges{mesh->medge, mesh->totedge};
+  Array<bool> visited(mesh->totvert, false);
+
+  std::priority_queue<VertPriority, std::vector<VertPriority>, std::greater<VertPriority>> queue;
+
+  for (const int start_vert_i : end_selection) {
+    r_cost[start_vert_i] = 0.0f;
+    queue.emplace(0.0f, start_vert_i);
+  }
+
+  while (!queue.empty()) {
+    const float cost_i = queue.top().first;
+    const int vert_i = queue.top().second;
+    queue.pop();
+    if (visited[vert_i]) {
+      continue;
+    }
+    visited[vert_i] = true;
+    const Span<int> incident_edge_indices = maps.edges_by_vertex_map[vert_i];
+    for (const int edge_i : incident_edge_indices) {
+      const MEdge &edge = edges[edge_i];
+      const int neighbor_vert_i = edge.v1 + edge.v2 - vert_i;
+      if (visited[neighbor_vert_i]) {
+        continue;
+      }
+      const float edge_cost = std::max(0.0f, input_cost[edge_i]);
+      const float new_neighbour_cost = cost_i + edge_cost;
+      if (new_neighbour_cost < r_cost[neighbor_vert_i]) {
+        r_cost[neighbor_vert_i] = new_neighbour_cost;
+        r_next_index[neighbor_vert_i] = vert_i;
+        queue.emplace(new_neighbour_cost, neighbor_vert_i);
+      }
+    }
+  }
+}
+
+class ShortestEdgePathsNextVertFieldInput final : public GeometryFieldInput {
+ private:
+  Field<bool> end_selection_;
+  Field<float> cost_;
+
+ public:
+  ShortestEdgePathsNextVertFieldInput(Field<bool> end_selection, Field<float> cost)
+      : GeometryFieldInput(CPPType::get<int>(), "Shortest Edge Paths Next Vertex Field"),
+        end_selection_(end_selection),
+        cost_(cost)
+  {
+    category_ = Category::Generated;
+  }
+
+  GVArray get_varray_for_context(const GeometryComponent &component,
+                                 const eAttrDomain domain,
+                                 [[maybe_unused]] IndexMask mask) const final
+  {
+    if (component.type() != GEO_COMPONENT_TYPE_MESH) {
+      return {};
+    }
+    const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component);
+    const Mesh *mesh = mesh_component.get_for_read();
+    if (mesh == nullptr) {
+      return {};
+    }
+    GeometryComponentFieldContext edge_context{component, ATTR_DOMAIN_EDGE};
+    fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge};
+    edge_evaluator.add(cost_);
+    edge_evaluator.evaluate();
+    const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
+
+    GeometryComponentFieldContext point_context{component, ATTR_DOMAIN_POINT};
+    fn::FieldEvaluator point_evaluator{point_context, mesh->totvert};
+    point_evaluator.add(end_selection_);
+    point_evaluator.evaluate();
+    const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
+
+    Array<int> next_index(mesh->totvert, -1);
+    Array<float> cost(mesh->totvert, FLT_MAX);
+
+    if (!end_selection.is_empty()) {
+      EdgeVertMap maps(mesh);
+      shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost);
+    }
+    threading::parallel_for(next_index.index_range(), 1024, [&](const IndexRange range) {
+      for (const int i : range) {
+        if (next_index[i] == -1) {
+          next_index[i] = i;
+        }
+      }
+    });
+    return component.attributes()->adapt_domain<int>(
+        VArray<int>::ForContainer(std::move(next_index)), ATTR_DOMAIN_POINT, domain);
+  }
+
+  uint64_t hash() const override
+  {
+    /* Some random constant hash. */
+    return 8466507837;
+  }
+
+  bool is_equal_to(const fn::FieldNode &other) const override
+  {
+    return dynamic_cast<const ShortestEdgePathsNextVertFieldInput *>(&other) != nullptr;
+  }
+};
+
+class ShortestEdgePathsCostFieldInput final : public GeometryFieldInput {
+ private:
+  Field<bool> end_selection_;
+  Field<float> cost_;
+
+ public:
+  ShortestEdgePathsCostFieldInput(Field<bool> end_selection, Field<float> cost)
+      : GeometryFieldInput(CPPType::get<float>(), "Shortest Edge Paths Cost Field"),
+        end_selection_(end_selection),
+        cost_(cost)
+  {
+    category_ = Category::Generated;
+  }
+
+  GVArray get_varray_for_context(const GeometryComponent &component,
+                                 const eAttrDomain domain,
+                                 [[maybe_unused]] IndexMask mask) const final
+  {
+    if (component.type() != GEO_COMPONENT_TYPE_MESH) {
+      return {};
+    }
+    const MeshComponent &mesh_component = static_cast<const MeshComponent &>(component);
+    const Mesh *mesh = mesh_component.get_for_read();
+    if (mesh == nullptr) {
+      return {};
+    }
+    GeometryComponentFieldContext edge_context{component, ATTR_DOMAIN_EDGE};
+    fn::FieldEvaluator edge_evaluator{edge_context, mesh->totedge};
+    edge_evaluator.add(cost_);
+    edge_evaluator.evaluate();
+    const VArray<float> input_cost = edge_evaluator.get_evaluated<float>(0);
+
+    GeometryComponentFieldContext point_context{component, ATTR_DOMAIN_POINT};
+    fn::FieldEvaluator point_evaluator{point_context, mesh->totvert};
+    point_evaluator.add(end_selection_);
+    point_evaluator.evaluate();
+    const IndexMask end_selection = point_evaluator.get_evaluated_as_mask(0);
+
+    Array<int> next_index(mesh->totvert, -1);
+    Array<float> cost(mesh->totvert, FLT_MAX);
+
+    if (!end_selection.is_empty()) {
+      EdgeVertMap maps(mesh);
+      shortest_paths(mesh, maps, end_selection, input_cost, next_index, cost);
+    }
+    threading::parallel_for(cost.index_range(), 1024, [&](const IndexRange range) {
+      for (const int i : range) {
+        if (cost[i] == FLT_MAX) {
+          cost[i] = 0;
+        }
+      }
+    });
+    return component.attributes()->adapt_domain<float>(
+        VArray<float>::ForContainer(std::move(cost)), ATTR_DOMAIN_POINT, domain);
+  }
+
+  uint64_t hash() const override
+  {
+    return get_default_hash_2(end_selection_, cost_);
+  }
+
+  bool is_equal_to(const fn::FieldNode &other) const override
+  {
+    return dynamic_cast<const ShortestEdgePathsCostFieldInput *>(&other) != nullptr;
+  }
+};
+
+static void node_geo_exec(GeoNodeExecParams params)
+{
+  Field<bool> end_selection = params.extract_input<Field<bool>>("End Vertex");
+  Field<float> cost = params.extract_input<Field<float>>("Edge Cost");
+
+  Field<int> next_vert_field{
+      std::make_shared<ShortestEdgePathsNextVertFieldInput>(end_selection, cost)};
+  Field<float> cost_field{std::make_shared<ShortestEdgePathsCostFieldInput>(end_selection, cost)};
+  params.set_output("Next Vertex Index", std::move(next_vert_field));
+  params.set_output("Total Cost", std::move(cost_field));
+}
+
+}  // namespace blender::nodes::node_geo_input_shortest_edge_paths_cc
+
+void register_node_type_geo_input_shortest_edge_paths()
+{
+  namespace file_ns = blender::nodes::node_geo_input_shortest_edge_paths_cc;
+
+  static bNodeType ntype;
+
+  geo_node_type_base(
+      &ntype, GEO_NODE_INPUT_SHORTEST_EDGE_PATHS, "Shortest Edge Paths", NODE_CLASS_INPUT);
+  ntype.declare = file_ns::node_declare;
+  ntype.geometry_node_execute = file_ns::node_geo_exec;
+  nodeRegisterType(&ntype);
+}