# Review 4: Paths in graphs: Questions

Recall the breadth-first search algorithm.

**def** `bfs`(`vertices`, `source`):

**for** `v` **in** `vertices`: `v`.`dist` = `INFINITY`

` source`.`dist` = `0`

`q` = `new queue`()

`q`.`add`(`source`)

**while not** `q`.`isEmpty`():

`u` = `q`.`remove`()

**for** `v` **in** `u`.`neighbors`:

**if** `v`.`dist` == `INFINITY`:

`v`.`dist` = `u`.`dist` + `1`

`q`.`add`(`v`)

A graph is said to be **bipartite** if the
vertices can be divided into two groups, and every edge connects
one group to another. Assuming we're given a graph where all
vertices are reachable from each other, how can we modify our breath-first
search code in order to determine whether our graph is
bipartite?

We can model a data network as a directed graph, with each vertex corresponding to a router and each edge corresponding to a connection between routers. In routing data through a network, there is a time delay associated with going through a connection — but there is also a time delay associated with passing through the router from one connection to the next. How can we use Dijkstra's algorithm so that it still finds the fastest route between two points in the network?

Suppose we have a weighted, undirected graph where all weights
are positive. Two sets of vertices have
been identified: One is a collection of possible start points,
and the other is a collection of possible end points. Each set
has √`n` vertices. We want to find the shortest path from any
single vertex in the start set to any vertex in the end set.

Give an `O`(`m` `log` `n`)-time
algorithm for solving this problem. (Recall that Dijkstra's algorithm
takes `O`(`m` `log` `n`) time,
but it works only from a single source to a single destination.)

Suppose we have a network of roads, where each road connects
two vertices and has an associated length. However, some of the
roads are known to be very rough, and we never want to take a
route that takes more than a single rough road. How can we
efficiently find the shortest route between two points
`s` and `t` that
doesn't traverse more than a single rough road?

Why use the Bellman-Ford algorithm for finding the shortest path between two vertices in a graph, when Dijkstra's algorithm does the same thing and is faster?

# Review 4: Paths in graphs: Solutions

The crucial change in the below implementation is the
addition of the

and of the two **elif**

lines. (Other changes are to the function parameters and
the addition of the assignment to **return**

.)`source`

**def** `is_bipartite`(`vertices`):

`source` = `vertices`[`0`]

**for** `v` **in** `vertices`: `v`.`dist` = `INFINITY`

` source`.`dist` = `0`

`q` = `new queue`()

`q`.`add`(`source`)

**while not** `q`.`isEmpty`():

`u` = `q`.`remove`()

**for** `v` **in** `u`.`neighbors`:

**if** `v`.`dist` == `INFINITY`:

`v`.`dist` = `u`.`dist` + `1`

`q`.`add`(`v`)

**elif** `v`.`dist` % `2` == `u`.`dist` % `2`:

**return False**

** return True**</`b`>

(Actually, the

condition can be just
“**elif**

”, since when BFS
discovers a previously-discovered vertex, the vertex's distance
will either be at the same distance from the source, or it will
be one link farther from the source.)`v`.`dist` == `u`.`dist`

We can add each router's delay to all its outgoing edges, and then we can run Dijkstra's algorithm on that.

We add a new vertex labeled α, which is connected to each start vertex with a zero-length edge. And we add a new vertex labeled ω, which is connected to each end vertex with a zero-length edge. Then we run Dijkstra's algorithm to find the shortest path from α to ω. The second step along the shortest path found is guaranteed to be a vertex from the start set, and the next-to-last step is guaranteed to be a vertex from the end set. The path found between the second vertex and the next-to-last vertex is the shortest path from the start set to the end set.

For each vertex `v`, we create two copies of the
vertex, `v`_{0} and `v`_{1}, which will be connected
with a directed edge of zero length from
`v`_{0} to `v`_{1}.
For each smooth road from `u` to `v`,
we include an edge from `u`_{0} to `v`_{0}
and from `u`_{1} to `v`_{1}.
For each rough road from `u` to `v`,
we include a directed edge from
`u`_{0} to `v`_{1} (and from
`v`_{0} to `u`_{1} if it is a two-way road).

We then use Dijkstra's algorithm on this new graph to find
the shortest path from
`s`_{0} to `t`_{1}. This path can only use
a single rough road, since taking a rough road takes it from the
`v`_{0}'s to `v`_{1}'s, and after that there
is no way to go back. If the shortest acceptable path takes no rough roads,
then it will take one of the zero-length directed edges from
some `v`_{0} to the corresponding `v`_{1}.

If the graph contains any edges with negative weights, then Dijkstra's algorithm does not find the correct answer. But Bellman-Ford does (assuming there are no cycles whose total weight is negative).