Getting My Hands Dirty with Floyd’s Algorithm
Okay, so the other day, I ran into a bit of a puzzle. I had this map, well, not a real map, more like a network diagram, you know? Bunch of points connected by lines, each line having a cost or distance. My task was simple, or so I thought: find the shortest path between every single pair of points. Not just from point A to point B, but A to C, A to D, B to C, B to D, you get the picture. All of them.
My first thought was, jeez, that’s a lot of paths. I could run Dijkstra’s algorithm starting from each point, right? But that felt kinda clunky. Running it over and over again… seemed like there oughta be a slicker way. Felt like I was gonna wear out my keyboard just coding that loop.
Then I remembered something from way back, this trick, I think it was Floyd’s algorithm? Or maybe Warshall was involved? Names get fuzzy. Let’s just call it the Floyd thingy for now. The idea sounded really neat: build it up step by step.
Setting Things Up
So, I decided to give it a shot. First things first, I needed to represent the network. An adjacency matrix seemed like the way to go. Made a grid, like a spreadsheet. The rows are starting points, columns are ending points.
- If there was a direct line from point ‘i’ to point ‘j’, I put its distance in the cell `(i, j)`.
- If ‘i’ and ‘j’ were the same point, the distance is obviously zero. So, `(i, i)` is 0.
- If there was no direct line from ‘i’ to ‘j’, I put a huge number in there. Basically, infinity. Gotta represent that somehow, just used a really big integer that wouldn’t mess up calculations.
This grid was my starting point. It held all the direct distances.
The Core Logic – Trying Stuff Out
Now for the clever part. The algorithm works by considering intermediate points. Let’s call ’em ‘k’. For every possible pair of points (‘i’ and ‘j’), it asks: “Is it shorter to go from ‘i’ to ‘j’ directly, OR is it shorter to go from ‘i’ to ‘k’ and then from ‘k’ to ‘j’?”
So I wrote the code. It ended up being three loops, nested inside each other. Crazy simple, actually.
Loop 1 (The ‘k’ loop): This one goes through every possible point that could be an intermediate stop. Let’s say point ‘k’.
Loop 2 (The ‘i’ loop): This one goes through every possible starting point ‘i’.
Loop 3 (The ‘j’ loop): This one goes through every possible ending point ‘j’.
Inside the innermost loop, I did the check:
current_distance = grid[i][j]
distance_through_k = grid[i][k] + grid[k][j]
if (distance_through_k < current_distance):
grid[i][j] = distance_through_k
That’s pretty much it! I just let these loops run. The beauty is, as the ‘k’ loop progresses, the grid gets updated with shorter paths found using the intermediate points processed so far. So, when ‘k’ is, say, 5, the check `grid[i][k] + grid[k][j]` uses the shortest paths to and from point 5 that might have already been discovered using points 0 through 4 as intermediates.
Finishing Up and Checking
Ran the code. It churned for a bit, not too long though, even for a decent number of points. When it finished, that same grid I started with now held all the shortest path distances between every pair of points. Cell `(i, j)` didn’t just have the direct distance anymore, it had the absolute shortest distance, whether it was direct or went through a bunch of other points.
Had to double-check a few paths manually on smaller examples just to be sure I hadn’t messed up the logic, especially with those ‘infinity’ values. Made sure adding ‘infinity’ didn’t accidentally create a ‘short’ path. It worked out fine.
Honestly, pretty satisfying. Felt way more elegant than running Dijkstra’s a million times. Just set it up, let the three loops run their course, and boom, all pairs shortest paths done. Simple, straightforward code once you get the matrix setup right. Definitely keeping this one in my toolkit.
