CIS 3223 Lab11 – Using Bellman-Ford Algorithm for
Shortest Path Analysis on Road Networks
DUE: (before the next lab, 10:30am Friday, April 17, 2008)
Bellman-Ford Algorithm
Bellman-Ford algorithm is an
efficient algorithm for finding shortest paths in graphs with negative weights.
It pseudo code is shown on p.588 of the Cormen
textbook and also in Chapter 4 of Dasgupta textbook. Therefore,
given a graph G with V nodes and weights w, the shortest paths from node s to any other node is obtained using the following Matlab-like pseudo code:
function [dst,
prev] = BF(G, w, s)
for i
= 1:V
dst(i) = 10e10; % a large number
prev(i) = -1; % a null
pointer
dst(s) = 0
repeat V-1 times
for every edge (u,v) of G
if dst(v) > dst(u)
+ w(u,v)
dst(v) = dst(u) + w(u,v)
prev(v) =
u
TASKS
1. (50%) Your goal is to implement in Matlab
a BF algorithm that, given a graph, finds the shortest paths from a given node s. The function definition is:
function [dst,
prev] = BF(G, s)
You should assume:
G to be a sparse
adjacency matrix of dimension V*V, where V is the number of graph nodes. The values of element G(i,j) is 0 if there is
no edge between nodes
i and j and w(i,j) if there is an edge from i to j;
s is the index of origin node;
dst is a V*1 vector of the
resulting shortest distances and prev a V*1 vector of the pointers
to (indices of) the previous node that allows reconstruction of the shortest
paths.
You
should implement an efficient BF Matlab algorithm that examines only the nonzero edges. 20%
of your grade will depend on the efficiency of your solution. Hint: you can represent a sparse matrix
G
of dimension V*V as a table of dimension E*3 listing the triples (u,
v, w(u,v)) as
[u,
v, w] = find(G);
Conversely,
you can create G from triples [u, v, w] as
G = spconvert([u,
v, w]);
Using
the E*3
table evaluation of all edges is done by a single for loop through the table. Evaluate the correctness of the
BF function. Use some of the example graphs covered in the lectures.
2. (30%)
You should apply the BF function to
search for the shortest paths in an imaginary road network you can download from
minnesota.mat.
The road network represents
[u,v] = find(A);
plot([xy(u,1)
xy(v,1)]',[xy(u,2) xy(v,2)]', 'k')
hold
plot(xy(:,1),xy(:,2),'.')
axis
equal
Your task is to find the shortest path
between the northernmost and the southernmost nodes of the graph when:
a) you assume the graph is undirected where all edges have the
same weight equal to 1, i.e., G = A.
b) you assume the edges represent distances between nodes. G(i,j) (if A(i,j) = 1) can be calculated as
G(i,j)
= sqrt((xy(i,1)-xy(j,1))^2 + (xy(i,2)-xy(j,2))^2);
Write a code that uses prev and xy to plot the shortest path
between origin node and destination node.
Plot the shortest paths in both cases and compare their shapes. How
different are they and why are they different? Explain.
3. (20%)
Observe that graphs from 2.a) and 2.b) are undirected with nonnegative weights.
Here, we assume the case where each node location has different elevation and
where we are using hybrid cars. The data with elevations of all nodes can be
downloaded from minnesota2.mat.
To visualize elevations you can
type:
pcolor(Xg,Yg,Zg)
shading('interp')
hold
plot([xy(i,1)
xy(j,1)]',[xy(i,2) xy(j,2)]', 'k')
colorbar
In
this case, uphill drive dries the batery, while
downhill drive charges the battery (we assume 80% of accumulated energy can be
used for battery charging). The goal is to find the shortest path that will
lead to the smallest energy consumption. By denoting Z(i) the elevation of node i, we can calculate edge weight using the following physics-based
formula:
if
A(i,j) == 0
G(i,j) = 0;
else
d(i,j) = sqrt((xy(i,1)-xy(j,1))^2
+ (xy(i,2)-xy(j,2))^2);
climb(i,j) = Z(j) - Z(i);
distance(i,j) = sqrt(climb(i,j)^2 + d(i,j)^2);
sinus(i,j) = climb(i,j) / sqrt(climb(i,j)^2 + d(i,j)^2);
if sinus(i,j) < 0
C =
0.8;
else
C = 1;
end
G(i,j) = distance(i,j) * C * sinus(i,j);
end
Create graph G using
this formula. Could you see why we
use this formula? Note that the resulting graph is directed graph (it matters
in which direction we are driving) with negative
edges, but without negative cycles. These properties make it possible to
use the Bellman-Ford algorithm without problems.
Your task is to find the shortest path
between the northernmost and the southernmost nodes of the resulting graph G. Plot the shortest path and compare it
with the paths obtained in Task 2. How different are they and why are they
different? Explain.