>An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality.

Well, I'm not trying to miss the bigger picture, but if you're going to scale that your O(n) algorithm will quickly take longer than a O(1) algorithm.

I mean, let's just take a hashtable as example. This hash takes 1 hour to complete while you can search the list in milliseconds.

But what if the list has billions and billions of entries and it takes longer than 1 hour?

As some others said, Big-O is not something you use to choose one algorithm over the other, it's something you use to choose an algorithm that scales well and has acceptable performance.

O(n) vs O(1) is a rather tame comparison, what if your competing algorithm is a O(n!) or worse?

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

Yes and its good to know the limits of Big O as you mentioned Big O tells you what an upper bound on something is but it will provide no answer as to which to which of two algorithms with the same upper bound will be faster. There is a field that deals with this and I watched some lectures by Robert Sedgewick called "Analytic Combinatorics" where he talks about a different analysis to do just that. He talks about being able to tell large institutional clients exactly how long an algorithm on a particular input will take and how important this was in the 1970s when computing power was much slower and far more expensive.