gk101

[(1, 2, 3), (2, 4, 5)] would result in a graph like this:

1 - 2 - 3

     \

      4 - 5

Building the (undirected) graph would take linear time, and once it is built, you can do a simple Depth First Search to mark all the connected components.

Yes, however big O notation isn't about which programs run faster, it's about how the runtime of a program changes in response to the input size

A few comments just in case this a critical part of your program, and if running it faster would help:

1. Using a heap with Dijkstra's algorithm would speed up your program

From your comment I am guessing you are using Dijkstra's algorithm without a heap, which gives O(n * m) for one source, and O(n^2 * m) for all sources (all pairs shortest path), where n is the number of nodes/vertices, and m is the number of edges

You would be able to improve that to O(m * n * lgn) by using a heap, which improves the time to run it by quite a lot in practice

2. The time it takes to run the program also depends on the density of your matrix:

In the case where the graph is sparse: m ~ n, and will result in O(n^2 * lgn) (or O(n^3) without a heap)

In the case where the graph is dense: m ~ n^2, and will result in O(n^3 * lgn) (or O(n^4) without a heap)

Compare the numbers above to O(n^3), which is the time complexity of Floyd-Warshall

So just in terms of time complexity, Floyd-Warshall would be faster in a dense graph

In fact he has a course on edx for this: https://www.edx.org/course/street-fighting-math-mitx-6-sfmx

Yup it's the same dude that ripped it off

The author gave a TED talk about this here: https://www.youtube.com/watch?v=Qy5A8dVYU3k

and yes, the default mode of the mind is to wander: http://en.wikipedia.org/wiki/Default_mode_network