3   Distance in Graphs
While the previous lecture studied just the connectivity properties of a graph, now we are going to investigate how "long" (short, actually) a connection in a graph is.
This naturally leads to the concept of graph distance, which has two variants: the simple one considering only the number of edges, while the weighted one having a "length" for each edge.
Brief outline of this lecture
• Distance in a graph, basic properties, triangle inequality.
• Graph metrics: all-pairs shortest distances.
• Dijkstra's algorithm for the shortest weighted distance in a graph.
• Route planning: a sketch of some advanced ideas.
x
V
Petr Hliněný,  FI MU Brno
: MA010: Distance in Graphs
3.1   Graph distance (unweighted)
Recall that a walk of length n in a graph G is an alternating sequence of vertices and edges v0, ei, vi, e2, v2,..., en, vn such that each &i has the ends Vj.
Definition 3.1. Distance dG(u,v) between two vertices u,v of a graph G is defined as the length of the shortest walk between u and v in G. If there is now walk between u, v, then we declare dG(u, v) = oo. c
Informally and naturally, the distance between u, v equals the least possible number of edges traversed from u to v. Specially dG(u,u) = 0.
Recall, moreover, that the shortest walk is always a path - Theorem 2.2.
Fact: The distance in an undirected graph is symmetric, i.e. dG(u,v) = dG(v,u). c
Lemma 3.2. The graph distance satisfies the triangle inequality:
Vu,v,w £ V(G) :   do(u, v) + dG(v,w) > do(u,w) .c
Proof. Easily; starting with a walk of length dG(u, v) from u to v, and appending a walk of length dG(v, w) from v to w, results in a walk of length dG(u, v) + dG(v,w) from u to w. This is an upper bound on the real distance from u to w. □
_Petr Hliněný,  FI MU Brno_2_FI: MA010: Distance in Graphs_
How to find the distance
Theorem 3.3. Let u,v,w be vertices of a connected graph G such that dG(u, v) < dG(u,w). Then the breadth-first search algorithm on G, starting from u, finds the vertex v before w. □
Proof. We apply induction on the distance dG(u, v): If dG(u, v) = 0, i.e. u = v, then it is trivial that v is found first. So let dG(u, v) = d > 0 and v' be a neighbour of v closer to u, which means dG(u, v') = d — 1. Analogously choose w' a neighbour of w closer to u. Then
do(u, w') > do(u, w) — 1 > do(u,v) — 1 = dG(u, v'),
and so v' has been found before w' by the inductive assumption. Hence v' has been stored into U before w', and (cf. FIFO) the neighbours of v' (v among them, but not w) are found before the neighbours of w' (such as w). □ □
Corollary 3.4. The breadth-first search algorithm on G correctly determines graph distances from the starting vertex.
Petr Hlineny,  FI MU Brno_3_FI: MA010: Distance in Graphs
Other related terms
Definition. Let G be a graph. We define, with respect to G, the following notions:
• The excentricity of a vertex exc(v) is the largest distance from v to another vertex; exc(v) = maxxeV(G) dG(v,x). c
• The diameter diam(G) of G is the largest excentricity over its vertices, and the radius rad(G) of G is the smallest excentricity over its vertices. c
• The center of G is the subset U C V (G) of vertices such that their excentricity equals rad(G).
Petr Hliněný,  Fl MU Brno
I: MAOlO: Distance in Graphs
3.2   All-pairs shortest distances
Definition: The metrics of a graph is the collection of distances between all pairs of its vertices. In other words, the metrics is a matrix d[,] such that d[i,j] is the distance from i to j. c
Method 3.5. Dynamic programming for all-pairs distances
• Initially, let d[i,j] be 1 (alternatively, the edge length of {vi; Vj}), or oo if vi; Vj are not adjacent. c
• After step t > 0 let it hold that d[i,j] is the shortest length of a walk between Vj, Vj such that its internal vert. are from (vo, vi,..., vt-1} (empty for t = 0).
• Moving from step t to t + 1, we update all the distances as:
— Either d[i,j] from the previous step is still optimal (the vertex vt does not help to obtain a shorter walk from vj to vj), or
— there is a shorter vj to vj walk using (also) the vertex vt which is, by the assumption at step t, of length d[i ,t] +d[t,j] . c
Theorem 3.6. Method 3.5 correctly computes the distance d[i,j] between each pair of vertices vi, vj in N = \V(G)\ steps.
in a graph G on the vertex set V(G) = (v0, v1,..., vN
V
Petr Hliněný,  Fl MU Brno
: MA010: Distance in Graphs
Remark: In a practical implementation we may use, say, HAX_INT/2 in place of oo.
Algorithm 3.7. Floyd-Warshall algorithm (cf. 3.5) input < the adjacency matrix G[,] of an N-vertex graph, such that the vertices of G are indexed as 0. . .N-1, and G[i,j]=1 if i,j adjacent and G[i,j]=0 otherwise;
for (i=0; i<N; for (j=0; j<N;
d[i,j] = (i==j?0:    (G[i,j]?   1: MAX_INT/2)); for (t=0; t<N; t++) {
for (i=0; i<N; for (j=0; j<N;
d[i,j] =min(d[i,j], d[i,t]+d[t,j]);
}
return ' The distance matrix d[,]'; c
Notice that this Algorithm 3.7 is extremely simple and relatively fast — it needs about N3 steps to get the whole distance matrix.
Its only problem is that all-pairs distances must be computed at the same time, even if we need to know just one distance. . .
Petr Hlineny,  FI MU Brno_6_FI: MA010: Distance in Graphs
3.3   Weighted distance in graphs
Definition: A weighted graph is a graph G together with a weighting w of the edges
by real numbers w : E(G) — R (edge lengths in this case).
A positively weighted graph G, w is such that w(e) > 0 for all edges e. c
Definition 3.8. (Weighted distance) Consider a positively weighted graph G, w. The length of the weighted walk S = v0, e\,v\, e2, v2,..., en, vn in G is the sum
dG(S) = w(ei) + w(e2) + • • • + w(e„) .
The weighted distance in G, w between a pair of vertices u,v is
dG(u,v) = min{dG(S) : S is a walk from u to v} .
All these terms naturally extend from graphs to directed graphs. c
Analogously to Section 3.1 we get:
Fact: The shortest walk in a positively weighted (di)graph is always a path. c
Lemma 3.9. The weighted distance in a positively weighted (di)graph satisfies the triangle inequality.
V
Petr Hliněný,  Fl MU Brno
: MA010: Distance in Graphs
See an example. . .
The distances between a-c and between b-c are 3. What about the a-b distance? □ Is it 6? □  No, the distance from a to b in the graph is 5 (traverse the "upper path").
Petr Hliněný,  FI MU Brno
I: MA010: Distance in Graphs
c
Negative edge-lengths?
What is the reason we are avoiding negative edge lengths?
Hence, what is the x-y distance this graph? Say, 3 or 1? c
No, it is —oo, precisely by Definition 3.8, and this answer does not sound nice.. . c Hence we have got a good reason not to consider negative edges in general.
Petr Hliněný,  Fl MU Brno
I: MA010: Distance in Graphs
X
3.4   Single-source shortest paths problem
This section deals with the more specific problem of finding the shortest distance between one pair of terminals in a graph (or, from a single source to all other vertices).
Remark: The coming Dijkstra's algorithm is, on one hand, slightly more involved than Algorithm 3.7, but it is significantly faster in the computation of single-source shortest distances, on the other hand. c
Dijkstra's algorithm:
• Is a variant of graph searching (related to BFS), in which every discovered vertex carries a variable keeping its temporary distance —the length of the shortest so far discovered walk reaching this vertex from the starting vertex. c
• We always pick from the depository the vertex with the shortest temporary distance. This is because no shorter walk may reach this vertex (assuming nonnegative edge lengths). c
• At the end of processing, the temporary distances become final shortest distances from the starting vertex (cf. Theorem 3.12).
Petr Hlineny,  FI MU Brno 10 FI: MA010: Distance in Graphs
Algorithm 3.10. Computing the single-source shortest paths (Dijkstra),
i.e. finding the shortest walk from u to v, or from u to all other vertices.
input < N-vertex graph given by adjacency mat. G[,] and cor. lengths len[,];
input < u,v, where u is the starting vertex and v the destination; c
// state[i] records the vertex processing state, dist[i] is the temporary distance for (i=0; i<N; i++) { dist[i] = MAX.INT; state[i] = 'init'; } dist[u] = 0;   depository D = {u};c while (state[v]!='processed') {
if (D==0)    return ' No path';
select m G D with minimal dist [m] ; c
// now updating all neighbours of m and their temporary distances for (i=0; i<N; if (G[m,i]) {
D = D U{i};
if (dist[m]+len[m,i]<dist[i]) { income[i] = m; dist[i] = dist[m]+len[m,i];
}
}
state[m] = 'processed';   D = D\{m};c
}
return 'A u-v path of length dist[v], stored in incm[] reversely';
Petr Hliněný,  FI MU Brno 11 FI: MA010: Distance in Graphs
Remark: Notice that Algorithm 3.10 works as-is also in directed graphs. c
Example 3.11. An illustration run of Dijkstra's Algorithm 3.10 from u to v in the following graph.
oo l        00 v
-----7«.
2   /   \ \
/ \
\ 2
5
V
3 \"
/
2 \
\
/
\
/ \ /' 2
0/ \/
V--------V
u 1 oc
Petr Hlineny,  FI MU Brn<
-I: MA010: Distance in Graphs
2
o
o
1
1
5
o
o
Fact: The number of steps performed by Algorithm 3.10 to find the shortest path from u to v is about N2 when N is the number of vertices (not so good...). c On the other hand, with a better implementation of the depository, one can achieve on sparse graphs runtime almost linear in the number of edges. c
Theorem 3.12. Every iteration of Algorithm 3.10 (since just after finishing the first while() loop) maintains an invariant that
• dist[i] is the length of a shortest path from u to i using only those internal vertices x of state[x]=='processed'. c
Proof: Briefly using mathematical induction:
• In the first iteration, the first vertex m=u is picked and processed, and its neighbours receive the correct straight distances (edge lengths). c
• In every next iteration, the picked vertex m is the nearest unprocessed one to the starting vertex u. Assuming nonnegative costs len[,], this certifies that no shorter walk from u to m may exist in the graph. c
On the other hand, any improved path from u to an unfinished vertex i passing through m has mi as the last edge (since the distance of m is not smaller than of the other finished vertices). Hence dist [i] is updated correctly in the algorithm.
□
V
Petr Hiineny,  FI MU Brr
I: MA010: Distance in Graphs
3.5   Advanced route planning
In some situations, there is a better alternative to ordinary Dijkstra's algorithm — the Algorithm A* which uses a suitable potential function to direct the search "towards the destination". Whenever we have a good "sense of direction" (e.g. in a topo-map navigation), A* can perform much better!
Algorithm A*
• It re-implements Dijkstra with suitably modified edge costs. c
• Let pv(x) be a potential function giving an arbitrary lower bound on the distance from x to the destination v. E.g., in a map navigation, pv(x) may be the Euclidean distance from x to v. c
• Each directed(!) edge xy of the weighted graph G,w gets a new cost
w'(xy) = w(xy) + pv(y) - pv(x) .
The potential pv is admissible when all w'(xy) > 0, i.e. w(xy) > pv(x) — pv(y). The above Euclidean potential is always admissible. c
• The modified length of any u-v walk S then is ď£ (S) = d£(S) + pv(v) — pv(u), which is a constant difference from dG(S)! Hence some S is optimal for the weighting w iff S is optimal for w'.
Here the Euclidean potential "strongly prefers" edges in the dest. direction.
Petr Hliněný,  Fl MU Brno_15_Fl: MA010: Distance in Graphs