Both can be implemented using exactly the same general algorithm:
Inputs: G: Graph s: Starting vertex (any for Prim, source for Dijkstra) f: a function that takes vertices u and v, returns a number Generic(G, s, f) Q = Enqueue all V with key = infinity, parent = null s.key = 0 While Q is not empty u = dequeue Q For each v in adj(u) if v is in Q and v.key > f(u,v) v.key = f(u,v) v.parent = u
For Prim, pass f = w(u, v) and for Dijkstra pass f = u.key + w(u, v) .
Another interesting thing: Generic above can also implement Breadth First Search (BFS), although this will be redundant because an expensive priority queue is not required. To enable the above general algorithm in BFS, go f = u.key + 1 , which will be the same as forcing all weights to 1 to be forced (that is, BFS gives the minimum number of edges needed to go from point A to B).
Intuition
Here is one good way to think of a general algorithm: we start with two buckets A and B. First, put all your vertices in B so that A bucket is empty. Then we move one vertex from B to A. Now we look at all the edges from the vertices in A intersecting the vertices in B. We selected one edge using some criteria from these cross-edges and move the corresponding vertex from B to A. Repeat this process until B becomes empty.
Most likely, to implement this idea, it will maintain a priority queue of edges for vertices in A intersecting with B. Obviously, this would be unpleasant if the graph were not sparse. So the question may be, can we maintain a vertex priority queue? In fact, we can, since our solution, finally, is which vertex to choose from B.
Historical context
Interestingly, the general version of the methodology that underlies both algorithms conceptually grows old until 1930, even when there were no electronic computers.
The story begins with Otakar Borevka, who needs an algorithm for a family friend who is trying to figure out how to connect cities in the country of Moravia (now part of the Czech Republic) with minimal cost of electric lines. He published his algorithm in 1926 in a journal devoted to mathematics, since then Computer Science did not exist. This drew attention to Wojtec Järnik, who thought about improving the Borůvka algorithm and published it in 1930. In fact, he discovered the same algorithm that we now know as the Prim algorithm, which reopened it in 1957.
Regardless of all this, in 1956 Dijkstra needed to write a program to demonstrate the capabilities of a new computer developed by his institute. He thought it would be great if the computer found a connection between the two cities of the Netherlands. He developed the algorithm in 20 minutes. He created a graph of 64 cities with some simplifications (because his computer was 6-bit) and wrote the code for this 1956 computer. However, he did not publish his algorithm, because basically there were no journals for computer science, and he thought that this might not be very important. The following year, he learned about the problem of connecting the terminals of new computers, so that the length of the wires was minimized. He thought about this problem and rediscovered the Jarník / Prim algorithm, which again uses the same technique as the shortest path algorithm that he discovered a year ago. He noted that both of his algorithms were developed without the use of a pen or paper. In 1959, he published both algorithms in a document that is only 2 and a half pages long.