Algorithmic Thinking: A Problem-Based Introduction by Daniel Zingaro

Author:Daniel Zingaro
Language: eng
Format: mobi, epub
ISBN: 9781718500815
Publisher: No Starch Press, Inc.
Published: 2021-11-15T00:00:00+00:00

As we discovered in “Shortest Paths in Weighted Graphs,” the shortest path from cell 1 to cell 4 is 17, but the shortest path from cell 4 to cell 1 is 36.

The shortest path from cell 1 to cell 4 uses the edges 1 → 3, 3 → 2, and 2 → 4. If we intend on starting Dijkstra’s algorithm from cell 4, then we need it to find edges 4 → 2, 2 → 3, and 3 → 1. Each of these edges is the reverse of an edge in the original graph. Figure 5-2 shows the reversed graph.

Figure 5-2: Mice Maze reversed graph

Now we can run Dijkstra’s algorithm—just one invocation of it!—from cell 4 to recover shortest paths to all nodes.

In terms of implementation, we’d need to produce the reversed graph instead of the original graph. This can be done in the main function (Listing 5-1), when reading the graph.

Instead of:

e->to_cell = to_cell;

e->length = length;

e->next = adj_list[from_cell];

adj_list[from_cell] = e;

we want this:

e->to_cell = from_cell;

e->length = length;

e->next = adj_list[to_cell];

adj_list[to_cell] = e;

That is, the edge now points to from_cell, and it gets added to the linked list for to_cell. If you make this change and adapt the code so that it invokes Dijkstra’s algorithm just once (from the exit cell), you’ll end up with a much faster program. Give it a try!

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.