It's not so much that it is "beautiful", but it is a remarkably simple algorithm that a human can follow manually. The reason it is efficient is easily understood (it's easy to see how we are able to "finalize" nodes because it's obvious there is no shorter path to that node), and it takes what would otherwise be a complicated task and makes it manageable.
Mind you, the “n” here is not the number of nodes!
More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the priority queue is implemented with a heap), where E is the number of edges and V is the number of nodes.
In the general case, E = O(V^2) (i.e. fully connected graph), so Dijkstra’s algorithm can calculate the shortest path to V nodes in O(V^2) time. It sounds less staggering this way.
And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! It’s pretty easy to see why: you can’t be sure you’ve actually found the shortest path until you’ve covered all the edges, because there’s always the possibility of a very large negative edge to be visited.
Dijkstra’s algorithm improves on this general case by exploiting the fact that the edges must have positive weight.
If there are negative edge-weights and cycles may occur, there is no shortest path between some nodes. You can keep going through a cycle whose total weight is negative getting "shorter" and "shorter".
It's like a race where one shortcut takes you back in time and leaves you where you started. You can use it to finish the race as far back in time before you started as you want.
Example:
V = { A, B, C }
E = { A -> B, B -> C, C -> A }
weight(A -> B) = 1
weight(B -> C) = 1
weight(C -> A) = -1
I mean, even Dijkstra himself came up with it because he needed it for a telecom gig. He can't have been the first one in the world who needed to find the shortest path in a graph. He just also happened to be a scientist, experienced in the whole "how to publish a paper" thing.