Shortest paths: Dijkstra, 0-1 BFS and Floyd-Warshall

Why this matters when you build with AI

Ask an AI tool for "the shortest path in this graph" and you will often get a Dijkstra function that looks right. It fails in three common ways. It stores "unreachable" as an int maximum, so adding an edge to it overflows and the distances turn negative. It runs Dijkstra when some edge weight is negative, which the method does not support. Or it runs Floyd-Warshall on 50000 vertices, which needs about 1.25 * 10^14 steps and never finishes.

You can catch all three in a few minutes. Know what each method assumes, write a brute force that is slow but obviously correct, and compare the two on many small random graphs. This lesson builds that habit together with the three methods.

A prompt that asks for the right thing, with the limits stated:

Write a C++17 function that returns the shortest distance from vertex s to every vertex.
Edge weights are integers from 0 to 10^9. There are up to 200000 vertices and 200000 edges.
Use long long for distances, say which value you use for "unreachable" and why,
state the time complexity, and state whether negative weights are allowed.

A good answer uses Dijkstra with a heap, a large long long value for unreachable (not INT_MAX), a time of about O((n + m) log m), and says negative weights are not allowed. Check each of those four things by reading the code, then run it against a brute force on small graphs (section "Check them against each other" below).

Terms used

A graph has vertices (numbered 0 to n - 1 here) and edges. A directed edge goes one way, from one vertex to another.
The weight of an edge is a number. The length of a path is the sum of the weights on it. The shortest distance from s to v is the smallest length of any path from s to v.
Unreachable means no path exists at all. We store it as INF, a value large enough that no real distance reaches it.
An adjacency list stores, for each vertex, the edges that leave it. Its size is O(n + m), where m is the number of edges. O(...) means the amount of work grows no faster than the given expression.
A binary heap is the structure behind C++ priority_queue. It gives the smallest item in O(log m) time, where m is the number of items in it.
A deque is a double-ended queue. You can add or remove an item at the front or the back in constant time.
Relaxing an edge from u to v with weight w means this: if dist[u] + w is smaller than dist[v], set dist[v] to dist[u] + w. All three methods are built from this one step. They differ only in the order in which they relax edges.

The idea: one small graph, relaxed in order

All code in this lesson reads the same small graph. Vertices are 0 to 5, the source is 0, and every edge goes one way.

0 -> 1 (weight 4)    0 -> 2 (weight 1)    2 -> 1 (weight 2)    1 -> 3 (weight 1)
2 -> 3 (weight 5)    3 -> 4 (weight 3)    4 -> 5 (weight 1)    2 -> 4 (weight 8)

At the start, dist[0] is 0 and every other distance is INF. Relaxing 0 -> 1 sets dist[1] to 4. Relaxing 0 -> 2 sets dist[2] to 1. Later, relaxing 2 -> 1 gives 1 + 2 = 3, which is better than 4, so dist[1] becomes 3. The best path to vertex 1 is therefore 0 -> 2 -> 1, not the direct edge. The final answer is:

vertex:    0  1  2  3  4  5
distance:  0  3  1  4  7  8

Every method below reaches this same table. The difference is how much work it does and which graphs it can handle.

Dijkstra with a binary heap

The rule

Dijkstra's method (Edsger Dijkstra described it in "A note on two problems in connexion with graphs", Numerische Mathematik, volume 1, 1959, pages 269 to 271) works like this. Keep a heap of pairs (distance, vertex). Repeatedly take the pair with the smallest distance, say vertex u. Relax every edge that leaves u, and push each vertex whose distance improved.

Why can we trust the vertex we take out? Take the first time we pop u. Any path from the source to u must at some point leave the set of popped vertices, through an unpopped vertex x. Every unpopped vertex has distance at least dist[u], because u had the smallest. Adding weights that are 0 or more cannot make the total smaller than dist[u]. So the value of dist[u] is final.

That argument needs the weights to be 0 or more. With a negative edge, adding a weight can make the total smaller, and a popped value can be wrong. Section "Common mistakes" shows a real case.

Lazy deletion

A heap does not let you lower the key of an item already inside it. So each time a distance improves, we push a new pair and leave the old one in the heap. When we pop a pair whose distance is larger than the current dist[u], that pair is stale, and we skip it. This trick is called lazy deletion. Each successful relaxation adds at most one heap entry, so there are at most m + 1 entries in total.

A trace on the example graph

Each line shows one pop from the heap, with the pairs it pushed.

pop (0, 0)   relax 0->1: push (4, 1)   relax 0->2: push (1, 2)
pop (1, 2)   relax 2->1: 1+2=3 < 4, push (3, 1)   relax 2->3: push (6, 3)   relax 2->4: push (9, 4)
pop (3, 1)   relax 1->3: 3+1=4 < 6, push (4, 3)
pop (4, 1)   stale, dist[1] is 3, skip
pop (4, 3)   relax 3->4: 4+3=7 < 9, push (7, 4)
pop (6, 3)   stale, dist[3] is 4, skip
pop (7, 4)   relax 4->5: push (8, 5)
pop (8, 5)   no edges leave 5
pop (9, 4)   stale, dist[4] is 7, skip
heap empty; distances 0, 3, 1, 4, 7, 8

The C++ code

The three methods live in one header, shortest.hpp, so the stress test can include it. The Dijkstra function is the first one. The header is shown in full in section "The C++17 code" below.

Dijkstra with lazy deletion takes O((n + m) log m) time and O(n + m) memory. This bound is what makes limits near 2 * 10^5 realistic in C++.

A Python version is fine for small inputs and for reading the logic. It is the same pattern with heapq:

Python · editable

Real output of that program (Python 3, run with python3 -I):

[0, 3, 1, 4, 7, 8]

Python may be too slow for the largest inputs in a contest. Write the final solution in C++ and use Python to check ideas on small cases.

0-1 BFS

The idea

Suppose every weight is 0 or 1. Then Dijkstra's heap is more work than needed. Keep a deque instead. An edge of weight 0 keeps the distance the same, so push its target to the front. An edge of weight 1 adds one, so push its target to the back. The deque always holds distances d and d + 1, with the smaller ones at the front, so popping from the front always gives the smallest distance.

A trace

Here is the example graph with weights 0 or 1. The topology is the same as before, but the weights are different.

0 -> 1 (1)    0 -> 2 (0)    2 -> 1 (0)    1 -> 3 (1)
2 -> 3 (1)    3 -> 4 (0)    4 -> 5 (1)    2 -> 4 (1)

The deque starts as [0].

pop 0 (dist 0): 0->1 gives 1, push back    deque [1]
                0->2 gives 0, push front   deque [2, 1]
pop 2 (dist 0): 2->1 gives 0 (better than 1), push front   deque [1, 1]
                2->3 gives 1, push back    deque [1, 1, 3]
                2->4 gives 1, push back    deque [1, 1, 3, 4]
pop 1 (dist 0): 1->3 gives 1, no change
pop 1 (dist 0): the second copy, same, no change
pop 3 (dist 1): 3->4 gives 1, no change
pop 4 (dist 1): 4->5 gives 2, push back
pop 5 (dist 2): no edges

Vertex 1 sits in the deque twice. The second copy does nothing new, and that is fine. The final distances are 0, 0, 0, 1, 1, 2 for vertices 0 to 5.

Each vertex can have its distance improved at most once, from d + 1 to d, so each vertex enters the deque at most twice. The total time is O(n + m).

The C++ code

The function is zero_one_bfs in shortest.hpp (section "The C++17 code"). Here is the program run on the 0/1 graph, saved as sp_demo01.txt, with the first line 6 8 0:

g++ -O2 -std=c++17 -Wall -Wextra -o sp sp_main.cpp
./sp 01bfs < sp_demo01.txt

Real output:

The same input gives the same answer with ./sp dijkstra, because Dijkstra is correct for weights 0 and 1 too. Dijkstra only costs more time.

What breaks

0-1 BFS is for weights 0 and 1 only. Weights of 2 or more break the rule that the deque holds only two distance values. The program still runs. In 3000 random graphs with weights from 0 to 3, the answers matched the brute force every time, so this test did not find a wrong answer. Passing a test does not prove the time bound, though. For weights above 1, use Dijkstra.

Floyd-Warshall

The idea

Floyd-Warshall (Floyd described the method in "Algorithm 97: Shortest path", Communications of the ACM, volume 5, number 6, 1962, page 345) finds the distance between every pair of vertices. It uses a dynamic programming idea that is easy to state. Number the vertices 0 to n - 1. Let d[i][j] be the best distance from i to j when the path may use only vertices 0 to k as stops on the way. Allowing one more stop vertex k gives:

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Before any stop vertex is allowed, the only paths are single edges. Worked example with three vertices and these edges: 0 -> 1 (weight 3), 1 -> 2 (weight 4), 0 -> 2 (weight 10). At the start, d[0][2] is 10. When vertex 1 becomes allowed as a stop, we try d[0][1] + d[1][2] = 3 + 4 = 7, which is smaller, so d[0][2] becomes 7. The table after all three steps is:

from 0: distance to 0 is 0, to 1 is 3, to 2 is 7

That is the real output of the program in the next block for source 0, so the hand trace and the code agree.

printf '3 3 0\n0 1 3\n1 2 4\n0 2 10\n' > tiny2.txt
./sp floyd < tiny2.txt

Real output:

0 0
1 3
2 7

The stop vertex k must be the outer loop. With i or j outside, the table is read before it holds the values for the current set of allowed stops, and the answers are wrong. In a test of 2000 random graphs with up to 6 vertices, the wrong loop order gave a different table in 206 of them.

Negative weights

Floyd-Warshall allows negative weights as long as no cycle has a negative total. If a negative cycle exists, the diagonal d[v][v] becomes negative for every vertex on it. Here is a 3-vertex cycle 0 -> 1 (weight 1), 1 -> 2 (weight -1), 2 -> 0 (weight -1). Its total weight is 1 - 1 - 1 = -1.

diagonal after Floyd-Warshall: -1 -1 -2

The numbers on the diagonal are not the cycle weight. They can be more negative than it. Only the sign is meaningful. Section "Bellman-Ford and negative cycles" in the next lesson explains how to find the vertices of such a cycle.

The C++ code

The function is floyd_warshall in shortest.hpp. It returns the full n by n matrix. The time is O(n^3) and the memory is O(n^2). For n = 400 that is about 6.4 * 10^7 inner steps, which is comfortable. For n = 2000 it is 8 * 10^9 steps, which is not. For n = 5000 the matrix alone is 25 million long long values, which is about 200 MB.

Which method fits your limits

Look at three things first: the sign of the weights, how many sources you need, and n and m. Then pick:

Situation	Method	Time
One source, all weights 0 or more	Dijkstra with a heap	O((n + m) log m)
One source, all weights 0 or 1	0-1 BFS	O(n + m)
All pairs, n up to a few hundred, no negative cycle	Floyd-Warshall	O(n^3)
All pairs, sparse graph, weights 0 or more	Dijkstra from every vertex	O(n m log m)
One source, some weights negative	Bellman-Ford (next lesson)	O(n m)

The "few hundred" depends on the time limit and the judge machine. Measure on your own machine before relying on a number. A contest with n and m near 10^5 usually needs one of the first two rows, applied from one source or from a few sources. Floyd-Warshall is for small n, where it is the simplest correct answer for every pair at once.

Check them against each other

A brute force is a program that is slow but hard to get wrong. For shortest paths, the brute force is this: relax every edge, n - 1 times. A shortest path with no negative cycle uses at most n - 1 edges, so n - 1 rounds are enough. The stress test in sp_stress.cpp builds random graphs with up to 9 vertices and weights from 0 to 9. It checks Dijkstra and Floyd-Warshall against the brute force, and 0-1 BFS against a brute force on the same graph with weights reduced to 0 or 1.

Commands and real output:

g++ -O2 -std=c++17 -Wall -Wextra -o sp_stress sp_stress.cpp
./sp_stress 7 3000
./sp_stress 99 3000

all 3000 random graphs agree: Dijkstra, 0-1 BFS, Floyd-Warshall and brute force
all 3000 random graphs agree: Dijkstra, 0-1 BFS, Floyd-Warshall and brute force

The seed fixes the graphs, so the same seed should print the same lines on your machine.

The C++17 code

These are the files the lesson uses. Put them in one folder. Compile with g++ -O2 -std=c++17 -Wall -Wextra. The code compiled with no warnings using g++ 15.2.0 on Linux.

shortest.hpp:

// shortest.hpp: three single-source or all-pairs shortest path routines.
#pragma once
#include <algorithm>
#include <deque>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
 
using ll = long long;
// "Unreachable" marker. It is large, but two of them added together still fit in a long long.
const ll INF = std::numeric_limits<ll>::max() / 4;
 
struct Edge {
    int to;
    ll w;
};
// g[u] lists the edges that leave u. Vertices are 0 .. g.size() - 1.
using Graph = std::vector<std::vector<Edge>>;
 
// Dijkstra. Every weight must be 0 or more. Time O((n + m) log m) with a binary heap.
std::vector<ll> dijkstra(const Graph& g, int src) {
    std::vector<ll> dist(g.size(), INF);
    using Item = std::pair<ll, int>;  // (distance when pushed, vertex)
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;  // lazy deletion: a newer, smaller entry for u exists
        for (const Edge& e : g[u]) {
            ll nd = d + e.w;
            if (nd < dist[e.to]) {
                dist[e.to] = nd;
                pq.push({nd, e.to});
            }
        }
    }
    return dist;
}
 
// 0-1 BFS. Every weight must be 0 or 1. Time O(n + m).
std::vector<ll> zero_one_bfs(const Graph& g, int src) {
    std::vector<ll> dist(g.size(), INF);
    std::deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (const Edge& e : g[u]) {
            ll nd = dist[u] + e.w;
            if (nd < dist[e.to]) {
                dist[e.to] = nd;
                if (e.w == 0)
                    dq.push_front(e.to);  // same distance: process it next
                else
                    dq.push_back(e.to);   // one more: process it after the current level
            }
        }
    }
    return dist;
}
 
// Floyd-Warshall. Returns the n x n matrix of shortest distances. Time O(n^3), memory O(n^2).
// Negative weights are fine as long as there is no negative cycle.
std::vector<std::vector<ll>> floyd_warshall(const Graph& g) {
    int n = (int)g.size();
    std::vector<std::vector<ll>> d(n, std::vector<ll>(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int u = 0; u < n; u++)
        for (const Edge& e : g[u]) d[u][e.to] = std::min(d[u][e.to], e.w);
    for (int k = 0; k < n; k++)  // k must be the outer loop
        for (int i = 0; i < n; i++) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (d[k][j] == INF) continue;
                d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    return d;
}

sp_main.cpp, the command-line driver. It reads n m s, then m edges, and prints the distances from s. Mode is dijkstra, 01bfs or floyd:

// sp_main.cpp: reads "n m s", then m lines "u v w" (directed edges). Prints distances from s.
// Usage: ./sp dijkstra|01bfs|floyd < input
#include <cstdio>
#include <string>
#include <vector>
 
#include "shortest.hpp"
 
int main(int argc, char** argv) {
    int n, m, s;
    if (scanf("%d %d %d", &n, &m, &s) != 3) return 1;
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        if (scanf("%d %d %lld", &u, &v, &w) != 3) return 1;
        g[u].push_back({v, w});
    }
    std::string mode = argc > 1 ? argv[1] : "dijkstra";
    std::vector<ll> dist;
    if (mode == "dijkstra")
        dist = dijkstra(g, s);
    else if (mode == "01bfs")
        dist = zero_one_bfs(g, s);
    else if (mode == "floyd")
        dist = floyd_warshall(g)[s];
    else
        return 2;
    for (int v = 0; v < n; v++) {
        if (dist[v] >= INF)
            printf("%d inf\n", v);
        else
            printf("%d %lld\n", v, dist[v]);
    }
    return 0;
}

The input file for the example graph is:

Real output of ./sp dijkstra < sp_demo.txt:

./sp floyd and ./sp dijkstra print the same table for this graph.

sp_stress.cpp, the random test. It uses the brute force from the section above:

// sp_stress.cpp: random small graphs. Checks Dijkstra, 0-1 BFS and Floyd-Warshall
// against a brute force that relaxes every edge n - 1 times.
// Usage: ./sp_stress [seed] [graphs]
#include <cstdio>
#include <cstdlib>
#include <random>
#include <vector>
 
#include "shortest.hpp"
 
struct Raw {
    int u, v;
    ll w;
};
 
std::vector<ll> brute(int n, const std::vector<Raw>& es, int s) {
    std::vector<ll> d(n, INF);
    d[s] = 0;
    for (int it = 0; it < n - 1; it++)
        for (const Raw& e : es)
            if (d[e.u] < INF && d[e.u] + e.w < d[e.v]) d[e.v] = d[e.u] + e.w;
    return d;
}
 
int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)std::strtoul(argv[1], nullptr, 10) : 1;
    int graphs = argc > 2 ? std::atoi(argv[2]) : 2000;
    std::mt19937 rng(seed);
    for (int t = 0; t < graphs; t++) {
        int n = 1 + (int)(rng() % 9);
        int m = (int)(rng() % (3 * n + 1));
        std::vector<Raw> es;
        for (int i = 0; i < m; i++) es.push_back({(int)(rng() % n), (int)(rng() % n), (ll)(rng() % 10)});
        int s = (int)(rng() % n);
 
        Graph g(n);
        for (const Raw& e : es) g[e.u].push_back({e.v, e.w});
        std::vector<Raw> es01 = es;
        for (Raw& e : es01) e.w %= 2;  // same shape, weights 0 or 1
        Graph g01(n);
        for (const Raw& e : es01) g01[e.u].push_back({e.v, e.w});
 
        std::vector<ll> ref = brute(n, es, s);
        std::vector<ll> ref01 = brute(n, es01, s);
        auto F = floyd_warshall(g);
 
        bool ok = dijkstra(g, s) == ref && F[s] == ref && zero_one_bfs(g01, s) == ref01;
        if (!ok) {
            printf("MISMATCH on graph %d (n=%d, m=%d, s=%d)\n", t, n, m, s);
            return 1;
        }
    }
    printf("all %d random graphs agree: Dijkstra, 0-1 BFS, Floyd-Warshall and brute force\n", graphs);
    return 0;
}

Common mistakes

Mistake 1: unreachable stored as int maximum. Symptom: a distance that should be large shows up as a negative number. The cause is INT_MAX + w overflowing. Either check dist[u] < INF before adding, or use a long long INF that is about a quarter of the maximum, as the header does. Both are needed in the code above: the Floyd loop checks d[i][k] == INF before it adds.

Mistake 2: Dijkstra with a negative edge. Here is a real case. Edges: 0 -> 1 (1), 0 -> 2 (2), 2 -> 1 (-5), 1 -> 3 (1). The true distance to vertex 3 is -2, through 0 -> 2 -> 1 -> 3. A version of Dijkstra that marks a vertex as done when it is popped gives a different answer:

brute force:            0 -3 2 -2
lazy dijkstra:          0 -3 2 -2
visited-array dijkstra: 0 -3 2 2

The visited-array version pops vertex 1 before the cheap route through vertex 2 is found. It then never looks at vertex 1 again, and vertex 3 gets 2 instead of -2. The lazy version happened to be right on this graph, but nothing guarantees that. Its running time can grow very large on some graphs with negative weights. Use Bellman-Ford from the next lesson.

Mistake 3: no stale check. If you leave out if (d > dist[u]) continue;, the answers stay the same, because a stale entry can only relax edges with values that are not better than what is already stored. The program just does more work. On a dense graph the extra work can cause a time limit error, and the cause is not obvious from the answers.

Mistake 4: 0-1 BFS with a weight of 2. Symptom: the program is correct on your samples but slow on a big test. The deque no longer holds only two distance values, so the O(n + m) bound is gone. Switch to Dijkstra.

Mistake 5: loop order in Floyd-Warshall. Symptom: answers differ from the brute force on small random graphs. This is the most common silent error in Floyd code. Put k outside.

Mistake 6: Floyd-Warshall on a large graph. For n = 50000 the loop runs about 1.25 * 10^14 times. The matrix alone needs n^2 = 2.5 * 10^9 entries, which is about 20 GB of long long. Symptom: a time limit error or a memory error, with no wrong answer. Use Dijkstra from each source instead, if the graph is sparse and the weights are 0 or more.

Checklist

Read the weights first. Any negative weight rules out Dijkstra and 0-1 BFS. Use Bellman-Ford.
Count the sources. One source, or all pairs?
If every weight is 0 or 1, use 0-1 BFS.
If n is a few hundred and you need all pairs, Floyd-Warshall is fine. Check n^3 against your time limit before you start.
Store unreachable as a large long long value, and check it before adding to it.
Put the stale check in Dijkstra.
Keep k as the outer loop in Floyd-Warshall.
Test on small random graphs against a brute force before you trust the code.

What was checked

All C++ code compiled with g++ 15.2.0 (Ubuntu) using -O2 -std=c++17 -Wall -Wextra, with no warnings.
The random stress test in sp_stress.cpp passed on 3000 graphs with seed 7 and 3000 with seed 99, against the brute force.
The wrong-answer examples above were run and the printed numbers were copied from the program output.
The Python sample was run with python3 -I.
The loop-order and 0-1 BFS weight-2 results come from separate random tests with 2000 and 3000 graphs. Those test programs are not part of the files shown.
I did not time the programs on large inputs. Running times depend on the machine, so treat the step counts above as arithmetic, not measurements.
The bibliographic details for the 1959 and 1962 papers were checked against publisher and bibliography records. I did not read the full text of either paper.

Summary

The three methods are the same idea, relaxing edges, in three different orders. Dijkstra takes the closest unfinished vertex next and needs non-negative weights. 0-1 BFS replaces the heap with a deque when weights are 0 or 1. Floyd-Warshall tries every vertex as a stop, which gives all pairs at once for small n. The weight signs and the limit on n decide which one to use.

Practice

Problem 1: trace from another source

Use the example graph, but start from vertex 3. Find every shortest distance from 3, and say which vertices cannot be reached. Then check your answer with ./sp dijkstra < sp_src3.txt, where sp_src3.txt has the same edges with 6 8 3 on the first line.

Show the answer

Hint: only edges that leave 3 can be used at the start, and 3 -> 4 -> 5 is the only way out of 3.

Answer: vertices 0, 1 and 2 are unreachable from 3. The distances are 0 for vertex 3, 3 for vertex 4 and 4 for vertex 5. The program prints 0 inf, 1 inf, 2 inf, 3 0, 4 3 and 5 4.

Problem 2: pick the method

A graph has n = 300 vertices and m = 40000 directed edges. Weights are integers from -20 to 20, and the graph has no negative cycle. You must answer 100000 queries of the form "shortest distance from u to v". Which method do you use, and why not the others?

Show the answer

Hint: count the work for each option, and notice that the queries can all be answered from one table.

Answer: Floyd-Warshall. It does 300^3 = 2.7 * 10^7 steps once, and then each query is a single lookup. Dijkstra is not allowed because of negative weights. Bellman-Ford from every source would do about n^2 m = 300 * 300 * 40000 = 3.6 * 10^9 steps, which is too slow for most judges.

Problem 3: cheapest path through a grid of costs

You are given an R by C grid of digits, each 0 or 1. Entering a cell costs the digit in that cell. The start cell (top left) is free. You may move up, down, left or right. Find the smallest total cost to reach the bottom-right cell. Example input: 3 4, then the rows 0100, 1101, 0010.

Show the answer

Hint: make each cell a vertex. The weight of the edge into a cell is that cell's digit, so the weights are 0 or 1.

Answer: 2. Two routes cost 2: down, down, right, right, right, and right, right, down, right, down. The program below prints 2 on the example. It agreed with a brute force relaxation on 400 random grids up to 5 by 5.

// grid01.cpp: practice solution. Input: R C, then R rows of C digits (0 or 1).
// Entering a cell costs its digit. The start cell is free. Moves: up, down, left, right.
#include <cstdio>
#include <deque>
#include <string>
#include <vector>
int main() {
    int R, C;
    if (scanf("%d %d", &R, &C) != 2) return 1;
    std::vector<std::string> grid(R);
    char buf[256];
    for (int r = 0; r < R; r++) {
        if (scanf("%255s", buf) != 1) return 1;
        grid[r] = buf;
    }
    const int INF = 1000000000;
    std::vector<int> dist(R * C, INF);
    std::deque<int> dq;
    dist[0] = 0;
    dq.push_back(0);
    const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
    while (!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        int r = cur / C, c = cur % C;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            int w = grid[nr][nc] - '0';
            int nxt = nr * C + nc;
            if (dist[cur] + w < dist[nxt]) {
                dist[nxt] = dist[cur] + w;
                if (w == 0) dq.push_front(nxt);
                else dq.push_back(nxt);
            }
        }
    }
    printf("%d\n", dist[R * C - 1]);
    return 0;
}

Real output on the example:

Problem 4: diameter from the table

Using the all-pairs table for the example graph (Floyd-Warshall), find the largest finite shortest distance. This is the diameter of the graph in the sense used here.

Show the answer

Hint: skip every entry that is INF, and look at all n^2 entries, not only row 0.

Answer: 8, from vertex 0 to vertex 5. The largest entry that is not unreachable in the full table is 8. A Python check of the Floyd-Warshall table printed diameter 8.

Problem 5: find a negative cycle with Floyd-Warshall

A graph has three vertices and edges 0 -> 1 (weight 1), 1 -> 2 (weight -1) and 2 -> 0 (weight -1). After Floyd-Warshall, which diagonal entries are negative? What does that tell you?

Show the answer

Hint: a negative diagonal entry at v means there is a negative closed walk through v.

Answer: all three. The printed diagonal was -1 -1 -2. The cycle has total weight -1, so the graph has a negative cycle, and every vertex on it has a negative diagonal entry. The exact values are not the cycle weight, so only the sign is useful.