2
$\begingroup$

At page 7 from these slides there is a Greedy algorithm I want to implement.

It says

let $P_i$ be the shortest path (if one exists) that [...]
connects some ($s_j$, $t_j$) pair that is not yet connected.

$(s_j,t_j)$ comes from a set of commodities.

Without getting into the theoretical implication of the whole algorithm, I only wonder how to implement such a statement.

It is stated to be greedy, hence it should have an easy implementation.

Is there a standard way to do that?

EDIT: Is there also any better reference than slides?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Slides seem intentionally vague. Check out for example Fleischer (2000) page 8. The weights of the graph are updated according only when they are used. It's a bit like approximate column generation. $\endgroup$
    – David Torres
    Oct 20, 2022 at 18:10

1 Answer 1

Reset to default
2
$\begingroup$

Only the outer algorithm is greedy, in the sense of removing the path links in each iteration and never looking back. Use any algorithm (like Dijkstra) to find a shortest path for each remaining $(s_j,t_j)$ in each iteration. As a possible speed-up, you can skip Dijkstra for all $j$ for which none of its shortest-path links have been removed because in that case the previously computed shortest path will still be shortest.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What about finding $P_i$. So far, I can only think of calculating all the possible shortest paths. $\endgroup$
    – Daniele Cuomo
    Oct 20, 2022 at 8:06
  • $\begingroup$ $P_i$ is not the shortest path between $(s_j,t_j)$. Rather $(s_j,t_j)$ is the couple connected by the shortest path $P_i$ in the graph. I can't figure out a better way to find this couple without computing all the paths per iteration. $\endgroup$
    – Daniele Cuomo
    Oct 20, 2022 at 10:48
  • $\begingroup$ I see. You are asking about a way to compute the minimum over $j$ of all shortest $s_j-t_j$ paths without explicitly recomputing them all. I amended my answer. $\endgroup$
    – RobPratt
    Oct 20, 2022 at 12:42
  • $\begingroup$ Thank you! Do you happen to know a better reference than the slides I shared?? $\endgroup$
    – Daniele Cuomo
    Oct 20, 2022 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.