Finding optimal subsequence in a path

Question

A path for the context of this question is a collection of points with integer coordinates v₁, v₂, v₃ ... v_n such that v₁ is connected to v₂, v₂ is connected to v₃ and so on. The path is non-cyclic and does not have any branches.
(By v and u are connected it means that the absolute difference between their either x or y coordinate is equal to 1)

We say there is a possible segment between v_i and v_j if they follow some criteria which is irrelevant to this question.
c_i represents the farthest point on the path in the forward direction such that there is a possible segment between v_i and c_i. (c_i lies ahead of v_i)
d_i represents the farthest point on the path in the backward direction such that there is a possible segment between v_i and d_i. (v_i lies ahead of d_i)
Note: If there is a possible segment between u and v then there is a possible segment between any of its sub segments.
The values of c_i and d_i are already calculated for each i.

For each pair v_i and v_j there is a penalty associated which also has been calculated for each i and j.

A sequence in a path is a collection of points of the path u₁, u₂, u₃ ... u_m (not necessarily connected) such that u₁ = v₁, u_m = v_n and there is a possible segment between each u_i and u_i+1.
Number of segments in such a cycle is (m-1).

The problem is to find the most optimal sequence which is a sequence having minimum number of segments possible and of all the such possible sequences have minimum sum of penalties of consecutive points in that sequence.

This problem is solved in a program called potrace which I am trying to implement but that implementation uses cyclic paths while my program uses non-cyclic. I also cannot understand how the potrace implementation below works in the first place.
In the implementation below clip0[i] represents c_i and clip1[i] represents d_i.
In potrace implementation cyclic means v₁ and v_n are also connected in the path.
Source Line 575
Documentation 2.2.4

/* calculate seg0[j] = longest path from 0 with j segments */
i = 0;
for (j=0; i<n; j++) {
  seg0[j] = i;
  i = clip0[i];
}
seg0[j] = n;
m = j;
/* calculate seg1[j] = longest path to n with m-j segments */
i = n;
for (j=m; j>0; j--) {
  seg1[j] = i;
  i = clip1[i];
}
seg1[0] = 0;
/* now find the shortest path with m segments, based on penalty3 */
/* note: the outer 2 loops jointly have at most n iterations, thus
   the worst-case behavior here is quadratic. In practice, it is
   close to linear since the inner loop tends to be short. */
pen[0]=0;
for (j=1; j<=m; j++) {
  for (i=seg1[j]; i<=seg0[j]; i++) {
    best = -1;
    for (k=seg0[j-1]; k>=clip1[i]; k--) {
    thispen = penalty3(pp, k, i) + pen[k];
    if (best < 0 || thispen < best) {
      prev[i] = k;
      best = thispen;
    }
    }
    pen[i] = best;
  }
}

pp->m = m;
SAFE_CALLOC(pp->po, m, int); // output
/* read off shortest path */
for (i=n, j=m-1; i>0; j--) {
  i = prev[i];
  pp->po[j] = i;
}

A sample input can be this.

EDIT 1: So when I implemented the same code for my case the last loop was breaking the code, the index value j was either becoming negative (without self looping) or i = prev[i] was self looping.
The penalty values are positive.

EDIT 2: I coded vaguely the Dijkstra's algorithm and it seems to be working.
I am providing my relevant bit of code below.

using Weight = std::pair<int, float>;
std::vector<std::vector<std::pair<int, Weight>>> graph;
graph.resize(n);
/*This takes O(n^2).*/
for (int i = 0; i < n; ++i) {
    for (int j = clip1[i]; j <= clip0[i]; ++j) {
        float pen = calculatePenalty(index, i, j);
        graph[i].emplace_back(j, Weight(1, pen));
        graph[j].emplace_back(i, Weight(1, pen));
    }
}

std::vector<bool> vis(n, false);
std::vector<Weight> dist(n, {10e5 + 1, 0.0f});
std::vector<int> prev(n, 0);
dist[0] = {0, 0.0f};

std::multiset<std::pair<Weight, int>> set;
set.insert({{0, 0.0f}, 0});

while (!set.empty()) {
    auto p = *set.begin();
    set.erase(set.begin());

    int x = p.second;
    Weight w0 = p.first;

    if (vis[x]) continue;
    vis[x] = true;

    for (auto v : graph[x]) {
        int e = v.first;
        Weight w = v.second;
        Weight w_ = {dist[x].first + w.first, dist[x].second + w.second};

        if (w_ < dist[e]) {
            prev[e] = x;
            dist[e] = w_;
            set.insert({dist[e], e});
        }

    }
}

for (int i = n - 1; i > 0;) {
    seq.push_back(i);
    i = prev[i];
}
seq.push_back(0);

If there are any errors in the above code then please correct it.
I think a number of improvements can be made in the above code.
The initialization of the graph itself has O(n^2) complexity. There should be an alternative way to do this part or the whole part.
Its also not so compact as the potrace counter part. A more compact implementation with better time complexity seems possible. If someone could provide some pseudocode in that direction than that would be appreciated.
Also in the potrace implementation it seems that the number of segments is precisely m. But when I compute m in my case and compare it with seg.size() - 1, it is not equal. (It is both greater and less in different cases but not by a large margin.)

Answer 1

The problem you're describing is the (single-source single-destination) shortest-path problem, where an edge's weight is (1, penalty) (and weights are summed elementwise and ordered lexically, so minimizing number of edges is first priority and minimizing total penalty is second priority). You can solve this problem in near-linear time with Dijkstra's algorithm if all your penalties are positive (or zero). In this case, you can prove that the shortest path will never repeat any vertices.

potrace's implementation looks roughly like Bellman-Ford's algorithm (in dynamic programming interpretation), which is a good approach if you have a mixture of positive and negative penalties (but unnecessarily slow if you have only positive penalties). In this case, the shortest path might repeat vertices, but when that happens, the path will actually repeat some vertices (a negative-weight cycle) infinitely many times, which is probably not what you want.