Scribd
Upload
2 views2 pages

Floyd-Warshall Algorithm Java Guide

This document provides a concise explanation of the Floyd-Warshall algorithm implemented in Java, detailing its purpose of computing shortest paths between all pairs of nodes in a weighted graph. It outlines the class structure, core methods, and key points, including handling of negative weights and safe infinity management. Additionally, it offers options for further enhancements such as cleaner OOP structure and Kotlin version.

Uploaded by

محمد لطیف عرفانی
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

Floyd-Warshall Algorithm Java Guide

This document provides a concise explanation of the Floyd-Warshall algorithm implemented in Java, detailing its purpose of computing shortest paths between all pairs of nodes in a weighted graph. It outlines the class structure, core methods, and key points, including handling of negative weights and safe infinity management. Additionally, it offers options for further enhancements such as cleaner OOP structure and Kotlin version.

Uploaded by

محمد لطیف عرفانی
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1 Here is a **clean, professional, and concise “Pro Note” explanation** for the code

you provided.
2 You can use it in documentation, teaching materials, or comments inside your project.
3
4 ---
5
6 # **📌 Pro Note — Floyd–Warshall Algorithm (Java Implementation)**
7
8 This class implements the **Floyd–Warshall algorithm**, a dynamic-programming
technique used to compute the **shortest paths between all pairs of nodes** in a
weighted graph.
9 It works for **directed graphs**, supports **positive and negative weights**, and
runs in **O(V³)** time.
10
11 ---
12
13 ## **🔧 Class Overview**
14
15 ### `FloydWarshall`
16
17 * Holds a list of `WeightedNode` objects that represent the graph.
18 * Computes the full **distance matrix**, showing the minimum distance from each node
to every other node.
19
20 ### **Constructor**
21
22 ```java
23 public FloydWarshall(ArrayList<WeightedNode> nodeList)
24 ```
25
26 Initializes the graph using a list of nodes.
27
28 ---
29
30 ## **🧠 Core Method: `floydWarshall()`**
31
32 This method calculates the shortest distance between all nodes using the following
steps:
33
34 ---
35
36 ### **1 ⃣ Build Initial Distance Matrix**
37
38 ```
39 V[i][j] =
40 0 (same node)
41 weight(i → j) (direct edge exists)
42 ∞ (no direct edge)
43 ```
44
45 Infinity is set to `Integer.MAX_VALUE / 10` to avoid arithmetic overflow when adding
distances.
46
47 ---
48
49 ### **2 ⃣ Run Floyd–Warshall Algorithm**
50
51 For each intermediate node `k`, update all `i → j` distances:
52
53 ```
54 if (V[i][j] > V[i][k] + V[k][j])
55 V[i][j] = V[i][k] + V[k][j]
56 ```
57
58 This step finds **better (shorter) paths** by passing through node `k`.
59
60 ---
61
62 ### **3 ⃣ Print Results**
63
64 Prints the shortest-distance table from every node to every other node.
65
66 ---
67
68 ## **📝 Adding Edges**
69
70 ```java
71 public void addWeightedEdge(int i, int j, int d)
72 ```
73
74 * Creates a weighted directed edge: `i → j`
75 * Updates both:
76
77 * `neighbors` list
78 * `weightMap`
79
80 ---
81
82 ## ✔ Key Points for Professionals
83
84 * Uses adjacency-list representation but converts it into a **distance matrix** for
the algorithm.
85 * Safe infinity handling avoids overflow during `V[i][k] + V[k][j]` calculations.
86 * Supports negative weights (as long as no negative cycles exist).
87 * Suitable for finding:
88
89 * All-pairs shortest paths
90 * Graph reachability
91 * Minimum distance matrices in routing systems
92
93 ---
94
95 If you want, I can also rewrite this with:
96 ✅ cleaner OOP structure
97 ✅ generics
98 ✅ Kotlin version
99 ✅ path reconstruction (not just minimum distances)
100 Just tell me!
101

You might also like