I have no idea why this question was considered off-topic for CSTheory. Certainly this question is very interesting to those who work in graph algorithms.
To that group, asking if there is a better solution to APSP than running BFS from each node, is equivalent to asking if there is an algorithm that runs in asymptotically less than $O(mn+n^2)$ time where $m$ is the number of edges and $n$ is the number of nodes. It is a major open problem to improve significantly on this running time.
Timothy Chan found some small algorithmic improvements in SODA'06 that may have promise in practice (he implemented them). See the paper:
Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523
In the undirected and unweighted case, one can solve the problem via reductions to matrix multiplication of $n \times n$ matrices (so theoretically, this means you can get $n^{2.376}$ time). If your graph is dense then this could be very useful. These algorithms are rather ingenious:
Zvi Galil, Oded Margalit: All Pairs Shortest Distances for Graphs with Small Integer Length Edges. Inf. Comput. 134(2): 103-139 (1997)
Zvi Galil, Oded Margalit: All Pairs Shortest Paths for Graphs with Small Integer Length Edges. J. Comput. Syst. Sci. 54(2): 243-254 (1997)
Raimund Seidel: On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. J. Comput. Syst. Sci. 51(3): 400-403 (1995)
Hopefully, expositions of the last three (or the papers themselves) can be found freely on the Web.
I'm not sure I completely get the question -- you are having trouble understanding Dijkstra's algorithm? The Wikipedia article is good, and there are many nice worked examples on the web. I would try to work through some of these examples, and then ask specific questions if you're still confused about how the algorithm works.
As for the homework problem you've quoted, here's a hint: any algorithm, Dijkstra or otherwise, for finding a shortest path will only work if such a path actually exists. Can you come up with an example of a connected weighted graph where no shortest path exists between some pair of nodes?
Best Answer
Although simple to implement, Dijkstra's shortest-path algorithm is not optimal. A guaranteed linear time, linear space (in the number of edges) algorithm is referenced by the Wikipedia article Shortest path problem as:
Thorup, Mikkel (1999) "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM 46 (3): p. 362–394
As Mikkel Thorup points out in the abstract of the above:
This effectively removes the dependency on number of vertices $V$ from $O(E + V\ln V)$ leaving only $O(E)$, where $E$ is the number of edges. Asano and Imai (2000) have an early but accessible account, Practical Efficiency of the Linear-Time Algorithm for the Single Source Shortest Path Problem. Slides from a 2009 talk by Nick Prühs are at Implementation of Thorup's Linear Time Algorithm for Undirected Single Source Shortest Paths With Positive Integer Weights.
We remark that linear-time is (quasi)optimal since in the worst case a shortest path consists of all the edges, and hence requires linear time to form the path.