DSA C#programming

Floyd Warshall All Pairs Shortest Path in DSA C#

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

Mental Model

We find the shortest paths between every pair of points by checking if going through a middle point is shorter than the direct path.

Analogy: Imagine you want to travel between every pair of cities. Sometimes, going through a third city is faster than going directly. We check all cities as possible middle stops to find the quickest routes.

   [0] -> [1] -> [2]
    ↑      ↑      ↑
   dist matrix with direct distances or infinity if no direct path

Dry Run Walkthrough

Input: Graph with 3 nodes and edges: 0->1 (4), 0->2 (11), 1->2 (2)

Goal: Find shortest distances between all pairs of nodes

Step 1: Initialize distance matrix with direct edges and 0 for same nodes

[0, 4, 11]
[∞, 0, 2]
[∞, ∞, 0]

Why: We start with known direct distances and zero for self to self

Step 2: Use node 0 as intermediate to update distances

[0, 4, 11]
[∞, 0, 2]
[∞, ∞, 0]

Why: No shorter paths found through node 0

Step 3: Use node 1 as intermediate to update distances

[0, 4, 6]
[∞, 0, 2]
[∞, ∞, 0]

Why: Distance from 0 to 2 updated from 11 to 6 via node 1 (4 + 2)

Step 4: Use node 2 as intermediate to update distances

[0, 4, 6]
[∞, 0, 2]
[∞, ∞, 0]

Why: No shorter paths found through node 2

Result:

[0, 4, 6]
[∞, 0, 2]
[∞, ∞, 0]
Shortest distances between all pairs found

Annotated Code

DSA C#

using System;

class FloydWarshall {
    const int INF = 99999;

    public static void FloydWarshallAlgorithm(int[,] graph, int V) {
        int[,] dist = new int[V, V];

        // Initialize distance matrix same as input graph
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i, j] = graph[i, j];
            }
        }

        // Update distances considering each node as intermediate
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i, k] != INF && dist[k, j] != INF && dist[i, k] + dist[k, j] < dist[i, j]) {
                        dist[i, j] = dist[i, k] + dist[k, j];
                    }
                }
            }
        }

        // Print the shortest distance matrix
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i, j] == INF) {
                    Console.Write("INF ");
                } else {
                    Console.Write(dist[i, j] + " ");
                }
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int V = 3;
        int INF = 99999;
        int[,] graph = {
            {0, 4, 11},
            {INF, 0, 2},
            {INF, INF, 0}
        };

        FloydWarshallAlgorithm(graph, V);
    }
}

dist[i, j] = graph[i, j];

copy initial direct distances into dist matrix

if (dist[i, k] != INF && dist[k, j] != INF && dist[i, k] + dist[k, j] < dist[i, j]) {

check if path through k is shorter than current dist[i,j]

dist[i, j] = dist[i, k] + dist[k, j];

update dist[i,j] to shorter path via k

OutputSuccess

0 4 6 INF 0 2 INF INF 0

Complexity Analysis

Time: O(V^3) because we check all pairs (i,j) for every intermediate node k

Space: O(V^2) because we store distances between all pairs in a matrix

vs Alternative: Compared to running Dijkstra from each node (O(V * (V^2)) for dense graphs), Floyd Warshall is simpler but slower for large graphs

Edge Cases

Graph with no edges except self loops

Distances remain zero for same nodes and infinity for others

DSA C#

dist[i, j] = graph[i, j];

Graph with negative edge weights but no negative cycles

Algorithm correctly finds shortest paths including negative edges

DSA C#

if (dist[i, k] != INF && dist[k, j] != INF && dist[i, k] + dist[k, j] < dist[i, j]) {

Graph with negative cycle

Algorithm does not detect negative cycles; distances may become incorrect

DSA C#

No explicit guard; Floyd Warshall needs extension to detect negative cycles

When to Use This Pattern

When asked to find shortest paths between all pairs of points in a graph, especially with possible negative edges, use Floyd Warshall because it systematically checks all intermediate nodes.

Common Mistakes

Mistake: Not initializing distance matrix correctly with direct edges and infinity for no direct path
Fix: Initialize dist matrix by copying graph and setting infinity where no direct edge exists

Mistake: Updating distances without checking if intermediate paths exist (infinity checks missing)
Fix: Add checks to ensure dist[i,k] and dist[k,j] are not infinity before adding

Summary

Finds shortest paths between every pair of nodes in a graph.

Use when you need all pairs shortest paths and graph may have negative edges but no negative cycles.

The key insight is checking if going through an intermediate node shortens the path between two nodes.

Practice

(1/5)

1. What is the main purpose of the Floyd Warshall algorithm in graph theory?

easy

A. To perform a depth-first search traversal

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

D. To find the shortest paths between all pairs of vertices in a weighted graph

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Floyd Warshall All Pairs Shortest Path in DSA C#

Practice

Solution

Step 1: Understand Floyd Warshall's goal

Step 2: Compare with other algorithms

Final Answer:

Quick Check:

Solution

Step 1: Understand initialization for Floyd Warshall

Step 2: Check each option

Final Answer:

Quick Check:

Solution

Step 1: Initialize dist matrix

Step 2: Apply Floyd Warshall updates

Final Answer:

Quick Check:

Solution

Step 1: Analyze loop order

Step 2: Identify impact of loop order

Final Answer:

Quick Check:

Solution

Step 1: Understand the graph and indexing

Step 2: Apply Floyd Warshall updates to find shortest path from 3 to 1

Final Answer:

Quick Check:

Ready to prove it?