This is a tree, Dijkstra is O(n^2) overkill. Trivial O(n) breadth-first search is enough.
EDIT: Start the BFS in any node with degree at least two.
EDIT2: Since the graph is not guaranteed to be a tree, use Dijkstra, if you want to optimize a little, you can first "strip" the graph all the vertices of degree one (for them, the path is trivial), including those that happen to acquire degree one due to stripping their ex-neighbours, and do the Dijkstra on the rest (which is exactly the "non-tree" part).
Plus, I would say you want paths from every node to every other, don't you? Dijsktra's algorithm does only paths from one to all others. Maybe do Floyd-Warshall algorithm on the stripped rest. Of course, if the topology is very dynamic, it is best to do the (stripping and) Dijkstra, ad hoc.