floyd-warshall algorithm in c – dead brainy, innit
intro
Oi, you lot! New to C and fancy summat a bit clever? We’re gonna sling together a lil program to do the Floyd-Warshall algorithm—ya know, that mad trick to find the shortest paths between all pairs of spots in a graph, like mapping the quickest pub crawl routes. It’s dead smart but proper doable—like when I was tryna figure the fastest way between boozers (gave up, too smashed). Great for getting yer head round 2D arrays and loops in C without a right faff. Let’s have a butcher’s!
code bit
Here’s the code—nowt posh, just a quick job I chucked together with a hard-coded graph. Shoved it in a box so it don’t look like a total shambles on yer blog. take a gander:
#define V 4 // vertices, innit
#define INF 99999 // big number for no path
void floydWarshall(int graph[V][V]) {
int dist[V][V]; // stash shortest paths
for(int i=0;i
}
}
for(int k=0;k
dist[i][k]+dist[k][j]
}
}
}
}
printf("shortest paths:\n");
for(int i=0;i
printf("INF ");
}
else {
printf("%d ",dist[i][j]);
}
}
printf("\n");
}
}
int main() { // nearly did void, ha!
int graph[V][V]={{0,4,INF,10}, // hard-coded graph
{INF,0,3,INF},
{INF,INF,0,6},
{INF,INF,INF,0}};
floydWarshall(graph); // crunch it
return 0; // forgot ; once, ugh!
}
what ya get
Here’s what it chucks out when ya run it. I hard-coded a lil graph—worked bang on, mate! (0-3 vertices, INF for no direct path)
0 4 7 10
INF 0 3 9
INF INF 0 6
INF INF INF 0
how it works, kinda
Right, let’s have a natter bout this like we’re slumped at the boozer with a pint—or a bag of pork scratchings, coz I’m Hank Marvin again. I’ll spill it like my tatty old notes from when I was faffing with C. It’s a doddle once ya clock it, swear down!
1. that `#include
This is me nicking my toolkit. `
2. `#define` bits
`V 4` sets 4 vertices—lil graph with 4 spots. `INF 99999` is a big number for “no path”—like saying “ain’t walking that far”!
3. `int main()` funtion
Gotta have a “main” to kick off—it’s like the door to my local. `int` means I’m lobbing a number out at the end (that `0` says “sorted, guv!”), and them curly `{}` lads keep it all snug. Nearly wrote `void main()`—old me was a right numpty!
4. boxes: `int graph[V][V]`
`graph[V][V]` is my lil grid—hard-coded with distances: 0 on diagonal (same spot), 4 from 0 to 1, 10 from 0 to 3, 3 from 1 to 2, 6 from 2 to 3, INF elsewhere—like pub distances!
5. `floydWarshall` funtion
Here’s the guts! `floydWarshall(int graph[V][V])` sorts it. `dist[V][V]` stashes the shortest paths—copies `graph` to start. Triple nested `for` loops—`k` as the middle mate, `i` start, `j` end. If `dist[i][k]` and `dist[k][j]` ain’t `INF` and their sum’s less than `dist[i][j]`, update it—shorter path via `k`! Like finding a quicker pub detour!
6. chucking it out: `printf` in `floydWarshall`
`printf("shortest paths:\n")` sets it up, then loops through `dist`. If `dist[i][j]==INF`, prints “INF”, else the number—`%d ` with a space, `\n` per row. Shows all shortest routes—like a pub crawl map!
7. `return 0` to scarper
That `return 0;` is me legging it, like, “Ta-ta, we’re done!” It’s a C thing—means it all went smooth as a greased weasel.
And that’s yer lot! A cracking lil program to do Floyd-Warshall for shortest paths. Faff with it—chuck in a daft graph, tweak it to say “pub hops” if ya fancy. First time I ran this, I saw 7 from 0 to 2 via 1—bang on, eh! You’re a star already, mate—keep smashing it! 😊 (Note: Hard-coded graph—real version’d take input, but this is pub-level quick!)
