---
title: "Shortest Paths with Negative Weights and Between All Pairs"
description: "Dijkstra's greedy choice fails once an edge can reduce a cost, so Bellman-Ford relaxes every edge n minus one times instead, and reports a negative cycle if anything still improves. Floyd-Warshall ans"
canonical: https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO
source: https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Shortest Paths with Negative Weights and Between All Pairs

Dijkstra's greedy choice fails once an edge can reduce a cost, so Bellman-Ford relaxes every edge n minus one times instead, and reports a negative cycle if anything still improves. Floyd-Warshall answers every pair at once by asking which intermediate vertices are allowed.

Subject: Computing · Area: Algorithms & Data Structures · Ages 20 to 22
Page: https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO

## Ready when they can

- Build a graph with a negative edge where Dijkstra returns the wrong distance
- Run Bellman-Ford and say what an improvement on the last pass proves
- Explain what the third index in the Floyd-Warshall recurrence stands for

## Lesson: When greedy paths fail

Dijkstra locks in each vertex greedily and never looks back. A negative edge can later undercut a locked distance. One graph with a single reducing edge is enough to return the wrong answer.

**Example.** Start S links to A at cost 5 and to B at cost 6, and B links to A at minus 4. Dijkstra locks A at 5, but the path through B costs 2. The greedy lock missed the cheaper route.

Bellman-Ford relaxes every edge n minus one times instead of locking anything. If any edge still improves on the last pass, a negative cycle exists. That improvement is the proof.

**Tip.** Floyd-Warshall answers every pair at once. Its third index names which intermediate vertices may be used so far. Grow the allowed set step by step and the table converges to all-pairs answers.

**Recap.** Greedy fails on negative edges, full relaxation detects cycles, and allowed vertices build all pairs.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Dijkstra's Shortest Path](https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL)
- [Dynamic Programming with a Capacity: Knapsack](https://lightmysky.com/learn/computing/dynamic-programming-with-a-capacity-knapsack-mt_T5pbU_DpdC)

## Opens up

- [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n)