static void shortest_path(const Mesh *mesh,
                          const Array<Vector<int>> &vert_to_neighbors_map,
                          Vector<float3> &path,
                          Vector<int> &offsets,
                          const int64_t start_index,
                          const IndexMask end_selection)
{
  Span<MVert> mvert{mesh->mvert, mesh->totvert};
  Array<float> cost(mesh->totvert);
  copy_vn_fl(cost.data(), cost.size(), FLT_MAX);
  Array<bool> visited(mesh->totvert);
  visited.fill(false);
  Array<int> prev(mesh->totvert);
  prev.fill(-1);

  std::priority_queue<VertPriority, std::vector<VertPriority>, VertPriority_greater> q;

  q.push(std::make_pair(0.0f, start_index));
  int i = 0;

  while (!q.empty()) {
    const float cost_i = q.top().first;
    i = q.top().second;
    q.pop();

    if (!visited[i]) {
      visited[i] = true;
      for (const int n : vert_to_neighbors_map[i]) {
        if (visited[n]) {
          continue;
        }

        float distance = math::length(float3(mvert[i].co) - float3(mvert[n].co));
        float cost_new = cost_i + distance;

        if (cost_new < cost[n]) {
          cost[n] = cost_new;
          prev[n] = i;
          q.push(std::make_pair(cost_new, n));
        }
      }
    }
  }

  for (const int j : end_selection.index_range()) {
    if (prev[end_selection[j]] != -1) {
      int count = 0;
      int iter = end_selection[j];
      do {
        count++;
        path.append(float3(mvert[iter].co));
      } while ((iter = prev[iter]) != -1);

      if (count > 0) {
        offsets.append(path.size() - count);
      }
    }
  }

  return;
}

static Curves *shortest_paths(const MeshComponent &component,
                              const IndexMask start_selection,
                              const IndexMask end_selection)
{
  const Mesh *mesh = component.get_for_read();
  const Array<Vector<int>> vert_to_neighbors_map = create_vert_to_neighbors_map(
      {mesh->mvert, mesh->totvert}, {mesh->medge, mesh->totedge});
  Vector<float3> points;
  Vector<int> offsets;

  for (const int i : start_selection.index_range()) {
    shortest_path(mesh, vert_to_neighbors_map, points, offsets, start_selection[i], end_selection);
  }

  Curves *curves_id = bke::curves_new_nomain(points.size(), offsets.size());
  bke::CurvesGeometry &curves = bke::CurvesGeometry::wrap(curves_id->geometry);

  offsets.append(points.size());
  curves.fill_curve_types(CURVE_TYPE_POLY);
  curves.offsets_for_write().copy_from(offsets);
  curves.cyclic_for_write().fill(false);
  curves.positions_for_write().copy_from(points);
  return curves_id;
}