Databases
StackOverflow2013
Postsdbo
PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
    primarykey
    data
    text
    <p>The way the Bellman Ford algorithm has been explained to me is that it goes through n-1 (with n being the number of nodes) iterations, updating the distance between nodes on each iteration. All graphical examples show the nodes initialized to infinity, and the ones closest to the source node being updated on the first iteration, but the rest remaining at infinity until an iteration occurs that reaches them.</p> <p>However, looking at code for the algorithm, such as that provided <a href="https://gist.github.com/701720" rel="nofollow">here</a>, I'm finding it hard to understand why all of the nodes that are more steps away than the number of iterations are not updated with the algorithm. For instance, if I'm on my second iteration and I have a node d that is only reachable through the path a-b-c-d, the examples I've read seem to indicate that d will not be updated until the 4th iteration. </p> <p>But the main relaxation function of the code:</p> <pre><code>def relax(node, neighbour, graph, d, p): # If the distance between the node and the neighbour is lower than the one I have now if d[neighbour] &gt; d[node] + graph[node][neighbour]: # Record this lower distance d[neighbour] = d[node] + graph[node][neighbour] p[neighbour] = node </code></pre> <p>updates based on information giving the weight and distance from the source of the predecessor node. If the algorithm iterates over each node in every iteration, what's to stop d from being properly updated in the FIRST iteration? For instance, if the algorithm iterated over the nodes in order a-b-c-d, I don't see why the algorithm wouldn't store the distance information for node b, move on to node c, store distance information for that, and finally reach d with enough information to calculate the shortest path IN THE FIRST ITERATION. </p> <p>I hope that made some kind of sense. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USuser1427661
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt *could* happen - but it is not *guaranteed*. You can only *guarantee* that you have shortest path of length up to `k` at the k'th iteration, not earlier.
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. USamit
    2. COSo the k iterations is really just an absolute ceiling on the number of iterations? Does that mean I could effectively create a tool that tracks the number of changes per iteration, and once that counter reaches 0, I could exit the iterations early?
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. USuser1427661
    3. CO@user1427661: Yes, that is typically one of the exit conditions for Bellman-Ford
      singulars
      1. PODifficulty Wrapping My Head Around the Iterations of Bellman Ford
      1. USBlueRaja - Danny Pflughoeft
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload