6
$\begingroup$

I see here and there, mostly in operations research courses in France that the Bellman-Ford algorithm related to shortest paths is called the Bellman-Kalaba algorithm. Could you explain the reason why it is called like that?

I searched and found a scientist named Roger Kalaba who seems to have been working with Bellman a lot. Why don't we call the Bellman-Ford-Kalaba algorithm? Is Bellman-Ford more spread than Bellman-Kalaba because Ford's contribution is bigger?

$\endgroup$
5
$\begingroup$

Interesting historical question. In Section 8.7, Chapter 8 of Algorithms (2019)1, Erickson notes that

The simplest implementation of Ford’s generic shortest-path algorithm was first sketched by Alfonso Shimbel in 1954, described in more detail by Edward Moore in 1957, and independently rediscovered by Max Woodbury and George Dantzig in 1957, by Richard Bellman in 1958, and by George Minty in 1958. (Neither Woodbury and Dantzig nor Minty published their algorithms.) In full compliance with Stigler’s Law, the algorithm is almost universally known as Bellman-Ford, because Bellman explicitly used Ford’s 1956 formulation of relaxing edges, although some authors refer to "Bellman-Kalaba" and a few early sources refer to "Bellman-Shimbel".

In particular, the name Bellman-Kalaba is occasionally used for the following reason:

This name is most likely a reference to Richard Bellman and Robert Kalaba’s monograph on dynamic programming and control theory2, which describes Bellman’s algorithm. Bellman and Kalaba also published an extension of Bellman’s algorithm in that computes $k$th shortest paths, for any constant $k$.3

References

[1] Erickson, J. (2019). Algorithms. University of Illinois Press.

[2] Bellman, R., Kalaba, R. E. (1965). Dynamic programming and modern control theory (Vol. 81). New York: Academic Press.

[3] Bellman, R., Kalaba, R. (1960). On $k$th best policies. Journal of the Society for Industrial and Applied Mathematics. 8(4):582-588.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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