[lorenzhs]

This is terrible. The charitable interpretation would be that Dijkstra's original paper in 1959 didn't use a priority queue, either. But given the strange hard-coded distance maximum of 100000, that Prim's MST algorithm is implemented the same way, and that Kruskal is implemented without a Union Find datastructure, I'm going to have to say it again: this is terrible. Don't use this for learning.

[stochastic_monk]

I'd instead recommend Boost's Graph Library. It's not an easy piece of code to understand, but they have everything from Flord-Warshall and Kruskal's to Min-Cut and Dijkstra's in very generic implementations.