Fun With Boolean Statements

A single Boolean expression can often be specified in multiple ways. For example, the expression A AND B is equivalent to the expression NOT (NOT A OR NOT B). One way to test the equivalence of two Boolean expressions is to create a table of every possible combination of the input variables along with the resulting value of the expression. In the example above:

A | B | A AND B

-----------------

F | F | F

T | F | F

F | T | F

T | T | T

And

A | B | NOT ((NOT A) OR (NOT B))

----------------------------------

F | F | F

T | F | F

F | T | F

T | T | T

Of course, a Boolean expression with N different input variables has 2^N different input combinations. Thus these tables can grow quickly, and it is often preferable to simplify the expressions mathematically.

The children of Bool enjoyed playing a particularly creative (and admittedly annoying) game. They would ask travelers simple questions that were phrased as complex Boolean expressions. They would then watch the traveler struggle to figure out how to answer the question. Usually, some amount of laughter would follow. It was like Bool's own form of logic-based prank calling.

The rules of the game were quite simple:

1) Start with a Boolean expression that asked a reasonable question.*

2) Make that expression as long as possible without changing the meaning.

Of the two rules, the second one was the easiest to follow. Newcomers to the game would dutifully draw out the logic tables for both expressions in order to demonstrate their equivalence. Experience players would produce simple, yet beautiful, proofs using simplification rules.

The first graders in Bool tended to stick with questions using double, triple, and quadruple negatives:

"Are you NOT NOT NOT NOT staying at the inn?" = "Are you staying at the inn?"

Unfortunately, the first graders still almost always managed to confuse themselves. They often had to resort to standing in the middle of the street, counting the number of negatives on their fingers, before deciding whether or not they could laugh at the traveler's answer.

By the time the kids reached second grade, they were using more complex rules, such as:

A AND TRUE = A

B AND FALSE = FALSE

C OR TRUE = TRUE

D OR FALSE = D

This would lead to all sorts of new fun, such as: "(Are you NOT stupid) OR (is the sun hot)?" which was TRUE regardless of the intelligence of the person. However, after being asked that question by a second grader, most travelers tended to feel stupid.

Of all the kids in Bool, Chuck was the best at this game. In fact, he was something of a legend at his elementary school. He had once caused a merchant to sputter in confusion by asking: "Is it really false that you: do not carry chocolate or do not carry gum?" By the time that the merchant figured out that Chuck was asking if he carried both chocolate and gum, Chuck and his friends were already laughing hysterically in the road.

Chuck's personal favorite was De Morgan's law, which stated:

NOT (A AND B) = (NOT A) OR (NOT B)

NOT (A OR B) = (NOT A) AND (NOT B)

In fact, DeMorgan's law led to Chuck's first classic: "Are you NOT (smart OR funny)?" which meant "(Are you NOT smart?) AND (Are you NOT funny?)" Even when someone answered the question correctly, Chuck found their expression hilarious.

Chuck's ultimate masterpiece was a thirty-eight clause phrase that asked about the traveler's path to Bool. It included no less than three different applications of De Morgan's law.

Thus it was much to Chuck's dismay when Ann passed through the town of Bool. Chuck sprung the question on her as she was finally leaving the town. He held is breath as he finished, waiting for the confused look that would ultimately prove him the master of complexifying Boolean expressions. Instead, Ann looked back at him and answered simply: "Yes. That is TRUE."

She waited for a moment to see why he had asked her an odd question. Then, after realizing that there was no followup question, Ann turned and continued her journey.

Chuck was devastated. He immediately went home and started work on a new, 50-clause, expression.

* "Reasonable" was much debated term and often led to hour long arguments. This matter was usually decided by a vote of the kids standing nearby or, in the case of ties, by a game of rocks-paper-scissors.

--------------------

For more Boolean fun, read about Ann's visit to the town of Bool.

The Game of Hamiltonian Paths: Part 9 of Ann's Visit to G'Raph

A Hamiltonian path visits each node in a graph exactly one time. The problem of determining whether a graph has a Hamiltonian path is NP-Hard.

"Mister Mayor, I think that there is a wizard casting spells on the scholars of G'Raph," Ann repeated. "Everyone to whom the wizard has spoken became obsessed with finding a polynomial solution to a specific NP-hard problem. Have you heard any stories about a stranger in a dark cloak asking scholars NP-hard computational problems?"

The mayor looked confused. "NP-Hard? I am not exactly sure what that means, but I had a man in a dark cloak ask me a hard question once."

"You did?" asked Ann, Edgar, and Florence in unison. None of them could hide the shocked looks on their faces.

"Yes," answered the mayor. "It was about twenty years ago -- right after I left school. He had just come from the library. I think he stopped to talk to Geoffrey about some salesman problem. Geoffrey was my favorite teacher, you know. He would always have the easiest tests. Anyway, the man asked me if I could solve a game: Find a path through G'Raph such that I go through each island at most one time."

"The Hamiltonian Path problem," stated Ann. "It is also NP-hard."

"It is related Geoffrey's traveling salesman problem," added Florence.

"But why did the wizard ask you about Hamiltonian paths?" Ann asked, trying to phrase the question tactfully. From her limited time with the mayor, he had yet to strike her as one of G'Raph's great scholars.

The mayor shrugged. "I don't know, but it sounded like a fun game."

"It is a popular game in G'Raph," Edgar agreed. "We played Hamiltonian paths as kids. We would draw out different hopscotch graphs and have to traverse them in Hamiltonian paths. Of course you were not allowed to solve them ahead of time. You had to determine the Hamiltonian path as you were hopping. If you got stuck or stepped on the same node twice, you were out."

Ann looked skeptical. "You really played that as a kid? That was how you spent your childhood?" she asked.

Edgar smiled at the fond memory. "Those were good times,” he answered.

"What did you say to the wizard?" Ann asked the mayor. "You did not solve it, did you?"

The mayor smiled. "I sure did. I told the man in the cloak: 'That's easy. I would just build a few more bridges.' The man left shortly after that. I think he said something about my future as a politician."

"That is cheating," objected Edgar. "You cannot add bridges in a game of Hamiltonian paths!"

"Mister Mayor," interrupted Ann. "Do you know anyone else who met the wizard?"

The mayor thought for a moment. "Not here in G'Raph. But I had an intern that told me a story that sounded similar to what you are claiming. He had a good friend in the town of Bool who became obsessed with one of these hard problems. What did you call them? NT? ND?"

"NP," offered Ann.

"Sure. Sure. Anyway, my intern's friend had a fun little problem called 3-SAT or something like that. Sounded like the type of thing you would find in the Sunday paper."

"The town of Bool? Are you sure?" asked Ann.

The mayor nodded. "You always know a Boolean when you meet one," Ann could not agree more.

After a few more minutes of discussion, Ann decided that she was not going to find any more answers here. She knew that there was a wizard that was casting spells on computational scholars; now she had to figure out why.

For the first time in her quest, Ann knew where to go next. She needed to pay a visit to the one place where she might find more information about NP-hard problems -- the library of Alexandria.

Read Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph. Or read about Ann's first (and highly unpleasant) visit to the city of Bool.

Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades: Part 8 of Ann's Visit to G'Raph

The minimum spanning tree of an undirected graph is the smallest set of edges such that all of the nodes are connected (if possible). Similarly, in a weighted graph, the minimum cost spanning tree is the set of edges with the minimum total weight such that they connect all of the nodes.

Ann went straight to city hall, where she hoped to find more information about the mysterious wizard. Florence and Edgar decided to join her. Or, more accurately, they decided to demonstrate how fast they could navigate G'Raph on their scooters. At least they left their map with Ann.

Ann found the mayor in his office, staring intently at a map of the G'Raph.

"Mayor, I have an important question for you," started Ann.

The mayor did not acknowledge her. He continued to stare at the map, mumbling to himself. Ann started to panic. Had the wizard been here?

After a moment, the mayor finally turned. "Edgar, this will never do. You need to redo it," he snapped.

"What?" asked Edgar. "That is exactly what you requested: the minimum weight spanning tree."

"The what?" asked the mayor with a confused look.

"Umm… I have an important question here," tried Ann, but nobody was paying attention.

"It is the set of bridges to upgrade," Florence explained to the mayor.

The mayor stood silently, not making the connection.



Florence continued. "You asked for the cheapest set of bridges to upgrade such that you could travel between any two islands by only crossing stone bridges. Since the price is determined by the length of the bridges, we found the shortest set of bridges."

"Why would you need to connect all the islands with stone bridges?" asked Ann, forgetting her original question for the moment.

"Nobody wants to be stuck at the dry cleaners after a dragon attack," offered Florence without additional explanation.

"We need a stone bridge between city hall and the library," said the mayor.

"That would add another 3 meters," countered Edgar. "It is cheaper to connect the inn and the dry cleaners." He pointed to the relevant bridges on the map to illustrate.

The mayor started to argue, but Ann cut him off.

"Interesting," interrupted Ann. "You found the set of bridges to replace that will connect all the islands together, while minimizing length. Did it take you long?"

"No," answered Florence. "I used Prim's algorithm.”

“Prim’s algorithm?” asked Ann.

“It is relatively simple algorithm,” said Florence. “You start with a random node, and add it to a new set of connected nodes. In this case, I 'randomly' chose the library.”

"Then you keep adding the closest node that is not already in the set. Here we first add the inn..."

"Then the brewery..."

"All very fascinating," interrupted the mayor. "But the library and city hall should have a new stone bridge between them."

"Edgar and Florence are correct," said Ann. "The lowest cost spanning tree does not have a new bridge there."

"But... I walk that way every day," said the mayor. "I am tired of the wobbly old bridge. We need something new."

Edgar, Florence, and Ann all looked at each other in silence. Edgar took a deep breath to start another algorithmic argument, but thought better of it. It was obvious that an algorithmic argument would not sway the mayor. Edgar decided to submit both prices and let the mayor choose.

Ann remembered why she had gone to the mayor's office in the first place.

"Mister Mayor, I think there is a wizard casting a spell on the scholars of G'Raph,” Ann blurted out. “I think the city and all of its scholars are in danger."

Behind Ann, Edgar and Florence gasped in unison.

To be continued in Part 9: The Game of Hamiltonian Paths.

---------------------------

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

Also check out the new illustrations in Bullies, Bubble Sort, and Soccer Tickets and Linked Lists, Kindergarten, and Ocean Voyages.

Panicked Depth First Search: Part 7 of Ann's Visit to G'Raph

Depth first search is a search algorithm that fully explores a single path before backtracking to test other paths. The algorithm operates in a recursive way, first exploring all of the options down one subpath before considering other subpaths. For example, on a graph the algorithm will explore the neighbors of a neighbor before returning to original node to test other direct neighbors. Unlike breadth first search, which uses a queue based approach to track unexplored states, depth first search uses an approach based on a stack.

Ann realized that she had made a critical mistake almost as soon as she left the library. In her rush to get to the school, she had neglected to bring a map with her. In any other town, this would not have been a major problem -- she would just run in the general direction of the school. But finding your way around in G'Raph was not that simple.

Ann stopped when she reached Thomas's farm. There were two paths in front of her, and she was not sure which way led to the school. She looked around for the farmer, but Thomas was not in his radish patch.

Making a quick decision, Ann chose the path out of Thomas's farm that was on her right. She ran over the bridge, and found herself at the local pottery kiln. An assortment of bowls were lined up outside the kiln. Judging from the quality of craftsmanship at least a few of the bowls must have been made by third graders at the school. Ann hoped that she was getting close.

Now Ann had another decision to make -- two new paths led away from the kiln. Again Ann chose the path to her right, and she ran over the bridge. This time the result was less promising. Ann had come to a dead end. She was on an island that appeared to be a mud quarry. There were no new bridges that might take her to the school.

Ann backtracked quickly, returning to the pottery kiln island.

She then ran down another bridge, arriving at a carrot farm. It was another dead end.

Ann backtracked to the pottery kiln again. This time there were no more paths to take, so she backtracked further. She returned to Thomas's farm. From the farm, she took the other bridge and arrived at another (smaller) radish farm. From the looks of it, this farm was decidedly less successful than Thomas's farm. Ann paused for the briefest moment to wonder what could cause the difference in radish growing performance between two almost indistinguishable islands of mud. Maybe it had something to do with crop rotation strategies.

Yet again, Ann was faced with a choice of bridges. She started with the path to her right. Much to her relief, this bridge led directly to the school.

Ann ran up to the school. Florence and Edgar were already there. Their scooters were parked nearby, and Edgar held a folded map of G'Raph in his hand. Ann cursed herself again for not having brought a map. She could have saved a lot of backtracking.

"You made it!" exclaimed Edgar. "I was afraid that you would get lost without a map."

"I did get lost." admitted Ann. "Or at least, I hit a few dead ends and had to backtrack."

"Ah… a depth first search." noted Florence. "Nice."

"Depth first search?" asked Ann. She was still a little out of breath from all the running.

"Depth first search is when you keep exploring along one path until you hit either a dead end or a node that you have seen before. Then you backtrack to the most recent decision point and try a different option. If there are no new options at that point, then you backtrack again." explained Edgar.

"Think about searching a binary tree." suggested Florence. "With depth first search, you keep exploring deeper and deeper until you come to a dead end."

"Or find what you are looking for." added Edgar.

"Yes. Good point." replied Florence. "You can also find what you are looking for. Edgar, remember that time we used depth first search on that choose your own adventure novel?"

"Fun times." answered Edgar.

Ann just nodded. She was too tired to appreciate the algorithmic beauty of her own frantic run. A map would have saved her from having to experience depth first search first hand.

The school's principal, having seen the group standing outside, came out to see what was going on.

"Have you seen a strange man in a dark cloak?" asked Ann without bothering to introduce herself.

"Umm… yes. Why do you ask?" asked the principal.

"Did he talk to anyone?" asked Ann, ignoring the principal's question.

"Yes. He talked with one of our star students, Elizabeth. He had some question about some sort of math problem." answered the principal. "I was there too, but honestly could not understand what he was talking about. Elizabeth seemed certain that she could figure it out though. She went right home to work on it. She is very bright, you know. Probably the best scholar that our school has ever taught. She will find the answer."

"Do you know what the question was?" asked Ann.

"It was something about islands and bridges. I think he called it 'vertex covering'. I had not heard of it before, but it sounded like fun."

Ann felt her stomach drop. She was familiar with the vertex covering problem from her own time in school. Like the traveling salesman problem, it was unknown whether the vertex covering problem had an efficient solution. The problem fell into a class of NP-hard problems.

Unless Ann missed her guess, Elizabeth had just fallen victim to the same spell as Geoffrey. G'Raph High School's star student was a risk of becoming unnaturally obsessed with a single NP-hard problem.

So far, the wizard had targeted two star scholars. Unfortunately, Ann had no idea why.

To be continued in Part 8: Minimum Spanning Trees, Prim's Algorithm, and Bridge Upgrades...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

--------------------

Find out more about breadth first search in: Breadth First Search and the Search for the Pig Thief.

Or find out about stacks and queues in: Stacks, Queues, Priority Queues, and the Prince's Complaint Line.

The Traveling Salesman's Problem: Part 6 of Ann's Visit to G'Raph

The traveling salesman problem is a route planning problem. The goal is to find the shortest path through a graph that visits each node exactly one time and returns to the starting node. The problem is also a classic example of a class of computational difficult problems, called NP-hard. There are no known efficient solutions (polynomial time) for solving NP-hard problems, and it has yet to be determined whether or not such a solution even exists.

Ann looked at the depressed scholar in the corner. "You have been working on the same problem for twenty-five years?" she asked.

"I am so close," he answered.

Behind her, Florence and Edgar had stopped arguing. They peeked their heads around the stack of books.

"Oh. I see you met Geoffrey," said Edgar. "Never mind him."

"I want to hear more about this problem," stated Ann. "What do you mean by shortest path?"

Geoffrey did not answer. He was hunched over his paper and mumbling to himself.

Ann turned back to Edgar and Florence. "You just told me about a shortest path algorithm,” she said.

"This is different," explained Florence. "The traveling salesman problem is a particularly difficult path planning problem. The goal is to find the shortest path through a graph that visits each node exactly once and returns to the starting node."

"Here are two example paths through G'Raph's school neighborhood," offered Edgar, drawing a crude sketch on a nearby blackboard.

Path 1

Path 2

"Both paths cross each node exactly once. Path 1 has a distance of 55 meters, and path 2 has a distance of 66 meters," he explained.

"That seems simple enough," commented Ann. "There is really no algorithm to solve it? Why not try all possible orderings of nodes? For each ordering, you could compute the total distance traveled if you visited the nodes in that order."

"There is no known efficient algorithm to solve it," explained Edgar. "No polynomial solution at least. The method you suggested would work, but it is factorial. You have to look at N! different orderings. For the 5 nodes in our simple example, there are 5! = 120 different permutations."

"Polynomial solution?" asked Ann.

"An algorithm where the running time scales polynomially with the size of the problem -- O(N^k) for some fixed value of k. For example linear algorithms O(N), quadratic algorithms O(N^2), and cubic algorithms O(N^3) are all polynomial. But the algorithm you suggested is O(N!); it scales as the factorial of N." Edgar explained.

Florence shrugged. "No one actually knows if there is an efficient solution or not. At least no one has found an efficient solution yet. There are good approximations and reasonable heuristics, of course, but no polynomial time algorithm."

"I played with it for a while," offered Edgar. "I never made much progress."

"Geoffrey has been working on it for twenty-five years?" asked Ann.

Both scholars nodded. "Ever since he met that man, Geoffrey has been unnaturally obsessed with this problem. He does not think about anything else. In the past, he would work on 3 or 4 different problems at the same time. It is as though he is under some sort of spell." Edgar explained.

Edgar's words sent a shiver through Ann. A vague memory floated through the back of her mind, but she was unable to latch onto it.

"Has anyone else met that man?" Ann asked.

Edgar shrugged. "I do not think so. Geoffrey said that he was probably a visiting salesman."

"He was selling questions," Geoffrey said quietly. Ann jumped at the sudden statement. Even though she had spoken to him only a minute ago, she had forgotten he was there.

"What did he look like?" asked Ann. The undefined memory continued nag at the back of her mind. She was miss a connection.

"Dark cloak and a large wooden staff that was covered with mathematical symbols," answered Geoffrey. "Never did see his face though."

"You only saw him that on time? Twenty-five years ago?" she confirmed. Why should an event from twenty-five years ago strike any memories with her?

"Three times," answered Geoffrey. "The first time was twenty-five years ago. Then, I saw him again ten years later. I was about to give up on the problem, but he found me and asked if I had solved it. That question rekindled the fire. I knew I could find a solution."

"And the third time?" asked Ann. She could feel a pit of fear building inside her, but she was not sure why.

"This morning," mumbled Geoffrey. "As I walked by the school, I saw him talking to some girl. He stopped for a moment and waved with his staff. I still have not found a solution yet, so I kept walking. I know I can find one. I am so close."

Ann did not wait for the rest of the story, she ran out the door and toward the school.

To be continued in Part 7: Panicked Depth First Search…

Follow Ann's Visit to G'Raph from the beginning with Part 1: The City of G'Raph.

A Disagreement Over Data Structures: Part 5 of Ann's Visit to the City of G'Raph

Graphs can be represented by a variety of data structures. Two common representations are: adjacency matrices and adjacency lists. Both data structures can handle directed, undirected, weighted, or unweighted edges. An adjacency matrix represents a graph as a matrix -- with one row and one column for each node. The matrix value of row i, column j is the weight of the edge from node i to node j (or 0/1 for unweighted graphs). An adjacency list maintains a separate list of neighbors for each node.

Ann had obviously touched upon a controversial question. Florence and Edgar stood on opposite sides of the room glaring at each other. The question had seemed innocent enough. "Do you always represent graphs with these illustrations?" Ann had asked.

Florence had quickly answered. "No. Those are only for illustration. Adjacency matrices work better."

And Edgar had snapped. "No. The correct answer is that adjacency lists are the preferred tools."

Then the glaring had begun.

"What are adjacency matrices and adjacency lists?" asked Ann, starting with the most basic question. Both scholars immediately rushed to explain their data structures. The resulting sound reminded Ann of two chipmunks fighting.

"One at a time, please." Ann pleaded. "Florence, why don't you start with adjacency matrices?"

Florence smiled. "They are very simple. Every row represents a node and every column represents a node. If there is an edge between two nodes, you put their weight in the corresponding element. So M[i][j] would store the weight of the edge from node i to node j. Here is an example of some of the islands of G'Raph."

"Adjacency matrices are wonderful." continued Florence. "See how it puts all of the information into a single convenient form. They are very simple representations. And you can perform a bunch of computations by just multiplying the matrices."

Ann nodded. It seemed sensible enough.

"Why aren't there ones along the diagonal? Obviously you can get from the library to the library." asked Ann.

"Depending on what you are trying to represent, self edges (or loops) can certainly make sense. In this case, I am only representing the existence of bridges. And there is no bridge from the library to the library." explained Florence.

"Okay. Now Edgar, can you tell me about adjacency lists?" asked Ann, turning to the other scholar.

"Certainly." started Edgar. "You start with a list of each node in the graph. Imagine a giant array or linked list with the name of each node in it. Then for each of those nodes, you keep a list of all the nodes to which it connects. For graphs with a few edges, it can use a lot less memory. You only store the edges that are there Here is an example."

Ann studied the example. "Both forms can represent the same graph exactly, correct?" asked Ann. Both scholars nodded,

"And both forms can do directed graphs as well?" asked Ann. Both scholars nodded.

"And they can both represent weighted edges?" asked Ann. Both scholars nodded.

"Then why are you fighting? It seems like they both do the same thing, but have different advantages. A matrix is simpler to specify, and a list can take less space. Is that really worth fighting over?" asked Ann. Both scholars nodded.

"Space matters!" cried Edgar. "Have you ever tried using your precious matrices to represent the entire pigeon network, Florence? There are thousands and thousands of nodes!"

"Simplicity matters too!" answered Florence "I can traverse my matrices with two fixed size FOR loops. You need to iterate over lists of different size. I have seen your implementations… they have POINTERS!"

"Better to have pointers than a row with ten thousand useless zeros!" responded Edgar.

The argument was getting heated. Ann backed away from the two scholars. She was afraid that one of them would eventually throw a coffee mug.

Then Ann heard a low sigh from the corner of the room. Turning away from the argument, Ann peaked around a very large stack of books. There, at a tiny desk in the corner, was the most depressed looking person that she had ever seen. He hunched over his desk, staring at a single sheet of paper on his desk and shaking his head.

"Hello?" Ann asked.

The man looked up at her blankly. "Both data structures are completely reasonable in their own way." he explained without bothering to introduce himself.

"I can see that." Ann confirmed. "I think they both have advantages and disadvantages."

The man just nodded. "I wish they would see that. They make such a terrible racket when they argue. I have important work to do, you know."

"I see. Can I ask what you are working on?" asked Ann.

"It is not done." he answered. "I have not figured it out yet."

"Oh. What is the problem, then?" Ann probed.

The man did not answer for a while. Behind her, Ann could hear Florence shouting something about invertability. Ann tried to ignore the argument.

Finally, the man gave Ann a sad look. "It is a really simple problem. I do not know why I have not been able to come up with a good solution. It really is quite simple. I just want an algorithm that will give me the shortest path through a graph such that the path visits each node exactly once."

Ann thought about this for a second. "Sounds like a good problem." she offered.

The man nodded. "I have been working at it for a while without any success. It all started a long time ago, when a man in a dark cloak first told me about the problem. I think he might have been a traveling salesman. I never did see his face though. He just told me that he had a problem that he needed the best scholar in G'Raph to solve. I was young and naive. I told him that I would have an efficient algorithm by the end of the week… that was twenty-five years ago."

To be continued in Part 6: The Traveling Salesman's Problem...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

-------

To learn more about matrices see Users, Peanut Vendors, and Matrix Indices.

To learn more about linked lists and arrays see Arrays, Linked Lists, and Zed's Coffee Shop or Linked Lists, Kindergarten and Ocean Voyages.

Dijkstra's Algorithm on Scooters: Part 4 of Ann's Visit to the Cit of G'Raph

Dijkstra's algorithm finds the shortest path from a given starting node to all of the other nodes in the graph. It requires that the weights of all edges are non-negative. It operates by maintaining a set of "visited" nodes and continually updating the tentative distance to all of the unvisited nodes. At each iteration, the closest unvisited node is added to the visited set and the distances to its unvisited neighbors are updated.

"We start by drawing up a list of all the islands in the entire city G'Raph." began Edgar. "We say that they are all 'unvisited' and have a tentative distance of infinity. Except the starting island itself; we give that a distance of zero. You can always get from here to here without moving."

"But distances of infinity are obviously not correct." interrupted Ann. She had walked from the inn to the library this morning, and it had not been an infinite distance.

"Of course it isn't correct." agreed Florence. "Dijkstra's algorithm keeps finding SHORTER paths to each node. So the distance will keep going down as we update our list. But since we have not found any paths at this point, we use the largest distance that we can. That way, any path we find will be better."

That explanation sounded reasonable to Ann. However, she did not quite see where this was going.

"Then the fun begins." continued Edgar. "We keep visiting islands until we have visited them all! This is the part where we get to drive around on scooters."

He took a deep breath before launching into the explanation.

"Each time we finish visiting a new island, we follow the same procedure:

1) We find the unvisited island that has the closest distance to our starting point.

2) We go to the island on our scooters. Usually, Florence and I like to race. That adds some more excitement.

3) We find all of the islands connected to the one we are on -- all of its neighbors -- and update their tentative distances. For each unvisited neighbor, we compute how far it is from the starting island IF we go through the current island. That is: the distance to the current island plus the distance to its neighbor. If this new distance is shorter, then that becomes the island's new tentative distance.

4) We mark the current island as visited, knowing that we now have the shortest path to that island.

Then we just repeat the procedure for the next closest unvisited island." described Edgar.

"And at the end, all of the islands have been visited, and we have a list of the shortest distances to each one." added Florence.

Ann looked at them blankly. "But I don't understand…" she started.

"An example will help." exclaimed Edgar. "Let's say that we start at the library. That becomes our current node -- with distance zero. Everything else starts with an infinite distance."

"Then we look at the neighbors and update their tentative distances." he continued. "In this case the inn is at most 5 meters away and city hall is at most 18 meters away."

"Now we are done with the library's node. So we mark it as 'visited' and move to the next closest island -- the inn." he continued. "In this case it is a quick scooter drive and not much of a race. But it will get more exciting."

"Since the inn is the closest unvisited island, we know we have found the shortest path to it. So we can update both its distance and its path." he continued.

"Yay!" added Florence quietly from the side.

Edgar gave her a strange look. "Anyway... We do the same thing here. Updating the neighbor's distances. The inn has three neighboring islands to consider: the library (which is already visited), the dry cleaners, and the brewery."

"Then we again move onto the closest unvisited node. This time it is the brewery." Edgar explained. "We repeat the process there, updating the neighbors."

"Then onto city hall. Here is where things get very interesting. It is a good race from brewery to city hall." Edgar made driving motions with his hands as he explained this. "Also, on the algorithmic side, the distance from the library to the dry cleaners is shorter if we go past the inn instead past city hall. So we do NOT update the distance to the dry cleaners in this case, because we have already found a shorter path."

"Then onto the dry cleaners. And so forth." he concluded with a wave of his hand.

"Yes." agreed Ann. "I understand that part. You are expanding the set of visited nodes, and you are maintaining tentative distances to nodes along the unvisited frontier. Each time you find a shorter path to a node, you update its distance. But what I do not understand is…"

"Exactly! You are quick." proclaimed Edgar. "I bet that you are confused by the question of whether there could be a shorter path through other unvisited notes."

"No. I am not." declared Ann. "There cannot be a shorter path, because you are taking the CLOSEST unvisited node. If there was a shorter path, then you would have to go through another node. But we already know that that other node is further away, because it is not the CLOSEST. It would be like saying that it is 200 miles to Athens and 100 miles to Atlantis, but the shortest path to Atlantis is through Athens. It would not make any sense. What I am confused about is…"

"Why we add the distances?" ventured Edgar. "Well, that is simple. The distance of going from A to B through node C is the distance from A to C plus the distance from B to C."

By now Ann was aggravated at the interruptions. "No! I have walked before. I know that when you walk over two bridges the total distances is the sum of the bridges."

Ann continued before she could be interrupted again. "I understand the algorithm. It is all very clear. What I want to know is: Why do you have to use scooters? You already have all the distances between islands written on this map. You could do all of this without traveling to the islands physically."

Now Edgar looked at Ann blankly. "Why would we do that?"

Ann sighed. "Because it is a lot faster to just mark nodes on a map as 'visited' instead of actually visiting them. You could do this entire algorithm on paper without leaving the library."

Edgar looked at Florence for help. "But, scooters are the best part. What fun would it be without scooters?"

Florence agreed. "That is why we call them 'visited' nodes, because we get to visit them. That is the whole point."

"All I am saying is that you do not need to physically drive there if you already have a representation of the graph." Ann noted.

"I don't think you really understand the concepts yet." ventured Edgar. "Let me start again. Dijkstra's algorithm finds the shortest distance from any starting node to all other nodes in the graph…"

Ann sighed and sat quietly in the corner. As Edgar and Florence re-explained how to add unvisited neighbors to the visited list, Ann started to daydream about racing through G'Raph on a scooter. There was something odd appealing about that approach.

To be continued in Part 5: A Disagreement over Data Structures...

Follow Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph.

--------------

Also, check out the new illustrations added to the following stories:

• Arrays, Linked Lists, and Zed's Coffee Shop
• Why Tailors Use Insertion Sort
• Swapping Array Values and the Swimmy Friends Pet Store