Bridge Weights: Part 3 of Ann's Visit to G'Raph

Graphs can have either weighted or unweighted edges. In graphs with weighted edges, each edge is associated with a real-valued weight. These weights can have different interpretations, depending on what the graph represents. For example, the weights might indicate the distance between two nodes in a transportation graph.

Two of G'Raph's scholars, Edgar and Florence, met Ann at the library. They were both visibly excited. They rarely had opportunities to show off their latest algorithms. They babbled about path routing and clustering. Their excitement was contagious.

After settling into a small, over-crowded office in the basement of the library, the scholars immediately pulled out a large stack of maps. Each map showed the same set of islands -- the city of G'Raph. However, each map contained different labels next to the bridges.

"What are all these labels?" asked Ann.

"It depends on map," answered Florence. "This one is labeled with the distance between the islands. We use it for path planning."

"I understand labeling the bridges with their lengths. That would allow you to compute the shortest path between two islands, right? How else would you label an edge?" asked Ann.

"Distance is only one concern," said Edgar. He had been sitting quietly in the corner, drinking his ninth cup of coffee. "There are hundreds of other things you might want to consider. For example, this map is labeled with the smelliness of each bridge. We use it for planning tours. Some of the bridges cross particularly nasty bits of swamp, you know. We want to avoid those bridges for tours, so we give them a high cost."

"This one is labeled with the estimated length of time needed to cross the bridge," interrupted Florence. She hoped to prevent Edgar from launching into a coffee fueled lecture of unpleasantness of living in a swamp. "We use it to compute different evacuation scenarios."

"Evacuation?" asked Ann in surprise. "Why would you need to evacuate?"

"There was some trouble a few years ago with a dragon," answered Florence. "We did not account for the time that it actually took to cross an old bridge. It totally gummed up the evacuation. Ten people got stuck at the dry cleaners after the dragon burned out a bridge. They were there for a week."

"They did not stop complaining for three months after that," added Edgar.

Ann nodded. The prospect of being stuck at the dry cleaners for a week seemed rather unpleasant. "Which map do you use most?" she asked.

"This one, of course," answered Florence and Edgar at the same time. They both pointed to a map labeled with the distances between islands.

"You use it for path planning? How do you do that?" prompted Ann. She was eager to learn more about the graph algorithms.

"Dijkstra's algorithm!" they answered at the same time.

"What is that?" asked Ann. Her knowledge of graph algorithms was admittedly not what it should be.

"Oh you will love it," proclaimed Edgar. "It involves scooters."

To be continued in Part 4: Dijkstra's Algorithm on Scooters...

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

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