Compute shortest paths across weighted graphs with detailed iteration tracking. Detect negative cycles with certainty. Review routes, relaxations, and final distances with confidence today.
| From | To | Weight | Expected Shortest Distance from A |
|---|---|---|---|
| A | B | 6 | B = 2 |
| A | D | 7 | D = 7 |
| B | C | 5 | C = 4 |
| B | D | 8 | A = 0 |
| B | E | -4 | E = -2 |
| C | B | -2 | Graph Type = Directed |
| D | C | -3 | Source = A |
| D | E | 9 | No reachable negative cycle |
This sample demonstrates negative weights without producing a reachable negative cycle.
The Bellman–Ford method relaxes every edge repeatedly. Each relaxation checks whether traveling through one vertex improves the best known distance to another vertex.
Relaxation rule:
d(v) = min(d(v), d(u) + w(u,v))
Where:
d(v) = current best distance to vertex v
d(u) = current best distance to vertex u
w(u,v) = edge weight from u to v
Process:
1. Set source distance to 0.
2. Set all other distances to infinity.
3. Relax every edge |V| - 1 times.
4. Run one more pass to detect any reachable negative cycle.
Path reconstruction uses the predecessor array. Each vertex stores the previous vertex that produced its current best distance.
It computes shortest-path distances from one source vertex to all other vertices. It also reconstructs routes, records passes, and checks for reachable negative cycles.
Yes. That is one of its main advantages. It works with negative weights, provided there is no reachable negative cycle affecting the requested shortest paths.
The calculator flags the cycle and marks affected vertices as risky. For those vertices, a true shortest path is undefined because repeated cycling can keep reducing total cost.
That means no valid route from the source reaches that vertex using the provided edges. Its distance remains infinity, and no predecessor chain can be formed.
Use directed mode when edge direction matters, such as one-way streets or state transitions. Use undirected mode when travel in both directions has equal weight.
Each pass relaxes all edges once. The algorithm needs up to |V|−1 passes because the longest simple shortest path can contain at most that many edges.
Yes. The detailed log and pass snapshots make it useful for learning relaxation mechanics, verifying manual solutions, and documenting intermediate algorithm states.
Enter one edge per line using from,to,weight or from to weight. For example: A,B,6 or A B 6. Weights may be positive, zero, or negative.
Important Note: All the Calculators listed in this site are for educational purpose only and we do not guarentee the accuracy of results. Please do consult with other sources as well.