@Magnus: Thanks for the comment. Note however that in K_n we cannot remove any single edge, because then we will loose all simple s-t paths through that edge. What Bellman-Ford do is they rather direct the edges, take multiple copies of them, and allow unmarked edges to represent s-t paths of all lengths. These multiple copies allow to even preserve the order of edges in the paths. Thus, my question actually is: can one do better than Bellman-Ford if one allows the edges of a path be represented in any order?

complex but intriguing. is this all assuming the graph has no negative cycle? is there some/any constraint on the edge weights, ie positive, negative, mixed?

@vzn: The question itself is for unweighted $K_n$. The Bellman-Ford DAG $G$ above represents all simple s-t paths in K_n of length at most $n+1$. Thus, $G$ is also a DP algorithm solving the shortest s-t path problem in K_n under all weigt-assignments producing no negative cycles. We only want to understand whether Bellman-Ford is optimal on problem instances on which it works (no negative cycles). This happens iff any DAG representing all simple s-t paths of length $\leq n+1$ in (unweighted) $K_n$ must have $\Omega(n^3)$ edges (this "iff" can be shown by using only 0 and 1 as weights).

1st you say $K_n$ is unweighted and then you seem to say its edges are weighted either 0/1...? re wikipedia, dijkstras algorithm is faster if there are no nonnegative edge weights & "thus bellman ford is primarily used for graphs with negative edge weights"

@vzn: A good point, thanks! Indeed, I should be more careful with my "motivation" of the purely graph-theoretic unweighted problem. My motivation was to prove/disprove that Bellman-Ford is optimal among DP algorithms. But is Dijkstra a "pure" DP algorithm? I mean, can it be given by a simple recursive relation? (Min of values of subproblems plus edge-lengths, as in the case of Bellman-Floyd. With no if-then-else comparisons of intermediate values.) Can Dijkstra be presented as solving the shortest path problem in a DAG?

all honesty, from what little understood so far, think its a creative angle & would like to dig into it with many more questions but one could easily imagine an entire paper proving the significantly noteworthy result if it holds, right? therefore alas it may not really be a great fit for this particular forum (and alas also there is no other place remotely like TCS.se elsewhere in cyberspace where it could fit better.. maybe a blog?)... would be interested in engaging in extended chat room discussion on the problem...

@vzn: Yes, the answer NO to my question (much fewer than $n^3$ edges in a DAG are enough, if the order of edges must not be preserved) would be worth even a paper. But I believe this is true only $< 0.1\%$. So, a YES answer would receive less attention. I am trying to figure out how to start a chat on this question. (Am new both in stackexchange as well as in algorithmics.)

hi in chat. yes also am not sure how to move questions to chat until the system gives that option when some # of comments is exceeded. can talk freely here without angry glares from other tcs.se users. am willing to stick with this worthwhile problem & continually revisit here if you are....

however would suggest that you consider rewriting the problem on a blog or web page instead of tcs.se where there is no way to edit it without it popping to the top of the home page [a sometimes-undesirable feature of stackexchange interface]... there may be a wiki somewhere where it could happen also... have you heard of polymath? they have a wiki, dont know if it is open to public or what....

re dijkstras algorithm vs bellman ford my understanding is that both work on weighted graphs and weighted DAGs, right? they should give equivalent answers for positive weights afaik...?

Yes, they both work definitely on DAGs. B&F reduce the shorttest s-t path problem in the cyclic graph ($K_n$)? As Bellman-Floyd does. I.e. just add the lengths of edges, and take their minimum. Dijkstra does something more: he computes the intermediate values, compares them with "best extensions", then updates the "temporal distances". So as it is, it is not a DP algorithm. I still wonder whether we can write Dijkstra as a rekursiv relation?

But even if we let "Dijkstra vs. Bellman-Ford" aside: can one label the wires of a DAG in such a way by the edges of K_n that all simple s-t paths remain intact, and no s-t path in the DAG is "wrong" (contains no s-t path of K_n)? I feel this is a question "in itself". Funniest, all depends on whether we want to preserve also the order of edges in K_n. I think - it does not depend. But how to prove this?

finding it hard to follow your current formulation would you be willing to rework it? wikipedia states bellman-ford is applied to a directed, weighted graph. but cant follow much in your question that makes the directions or weighting clear.... it seems like you are more talking about undirected, unweighted graphs/DAGs...? ps would you be willing to look at a monotone circuit idea for NP vs P/poly on my blog sometime? =)

Directed or undirected, this is not a question. Paths are always directed. In my question one may assume K_n being a complete directed graph (with forth and back edge between any two nodes). I will try to find the "monotone circuit idea for NP vs P/poly".

P.S. I would not try to attack the NP vs P/poly, unless we can not understand the "trivial" things like optimality of Bellman-Ford. Circuits (monotone or not) are much more dangereous (and clever) guys.

?!? you said K_n is undirected in the 1st line of your question....? [re circuits, yes, as one eminent authority aptly calls them, "the adversary", havent written up the monotone circuit idea yet, it will take awhile! & will let you know sometime, thx]

am not an expert on Dijkstra vs Bellman-Ford but do the algorithms make any sense on on undirected graphs?