Algorithms in a Nutshell

(^160) | Chapter 6: Graph Algorithms
In this presentation we tried to minimize the distance traversed. In other applica-
tions we might replace distance with time (e.g., deliver a packet over a network as
quickly as possible) or with cost (e.g., given the costs of legs of commercial flights,
find the cheapest way to fly from St. Johnsbury to Waco). Solutions to these prob-
lems also correspond to shortest paths.
We may seek the most reliable path to send a message from one point to another
through a network where we know the probability that any leg of a transmission
delivers the message correctly. The probability of any path (sequence of legs)
delivering a message correctly is the product of all the probabilities along the path.
Using the same technique that made multiplication possible on a slide rule, we
can replace the probability on each edge with minus the logarithm of the proba-
bility. The shortest path in this new graph corresponds to the most reliable path
in the original graph.
DIJKSTRA’S ALGORITHM cannot be used when edge weights are negative.
However, BELLMAN-FORD(shown in Example 6-6 and Figure 6-16) can be used
as long as there is no cycle of negative weight—that is, a cycle in the graph whose
edge weights sum to a value less than zero. The concept of a “shortest path” is
meaningless when such a cycle exists. Although the sample graph in Figure 6-13
contains a cycle involving vertices {1,3,2}, the edge weights are positive, so
BELLMAN-FORDand DIJKSTRA’SALGORITHM continue to work.
Example 6-6. Bellman-Ford algorithm for single source shortest path
#include "Graph.h"
/**

• Given directed, weighted graph, compute shortest distance to all vertices


• in graph (dist) and record predecessor links for all vertices (pred) to


• be able to recreate these paths. Graph weights can be negative so long


• as there are no negative cycles.
  /
  void singleSourceShortest(Graph const &graph, int s, / in /
  vector &dist, vector &pred){ / out */
  // initialize dist[] and pred[] arrays.
  const int n = graph.numVertices( );
  pred.assign(n, -1);
  dist.assign(n, numeric_limits::max( ));
  dist[s] = 0;
  // After n-1 times we can be guaranteed distances from s to all
  // vertices are properly computed to be shortest. So on the nth
  // pass, a change to any value guarantees there is negative cycle.
  // Leave early if no changes are made.
  for (int i = 1; i <= n; i++) {
  bool failOnUpdate = (i == n);
  bool leaveEarly = true;
  // Process each vertex, u, and its respective edges to see if
  // some edge (u,v) realizes a shorter distance from s->v by going
  // through s->u->v. Use longs to prevent overflow.
  Algorithms in a Nutshell
  Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
  9780596516246 Publisher: O'Reilly Media, Inc.
  Prepared for Ming Yi, Safari ID: [email protected]
  Licensed by Ming Yi
  Print Publication Date: 2008/10/21 User number: 594243
  © 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use