Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
Don’t worry, I’ll revisit the “Sweden tour” problem in Chapter 11.
The min-cost bipartite matching problem, discussed in Chapter 10.
Well, I’m assuming distinct distances here. If more than one node has the same distance, you could have more than one candidate. Exercise 9-2 asks you to show what happens then.
You may notice that edges that go back into S are also relaxed here in order to keep the code simple. That has no effect on correctness or asymptotic running time, but you’re free to rewrite the code to skip these nodes if you want.
In a more conventional version of Dijkstra’s algorithm, where each node is just added once but its estimate is modified inside the heap, you could say this path is ignored if some better estimate comes along and overwrites it.
As you can see, I just instantiate object to create the node s. Each such instance is unique (that is, they aren’t equal under ==), which makes them useful for added dummy nodes, as well as other forms of sentinel objects, which need to be different from all legal values.
A common criterion for calling a graph sparse is that m is O( n), for example. In this case, though, Johnson’s will (asymptotically) match Floyd-Warshall as long as m is O( n 2/lg n), which allows for quite a lot of edges. On the other hand, Floyd-Warshall has very low constant overhead.
You could do the same memory saving in the memoized version, too. See Exercise 9-7.
Actually, as I was writing this chapter for the first edition, it was proven (using 35 years of CPU-time) that the most difficult positions of Rubik’s Cube require 20 moves (see www.cube20.org ).
For example, when working with my alchemical example, I removed words such as algedo and dola.
That number is 100, not the factorial of 100. (And most certainly not the 11th power of the factorial of 100.)
- From A to B with Edsger and Friends
Magnus Lie Hetland
- Sequence number
- Chapter number
- Chapter 9