BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Wednesday , June 28 2017
Home / Discrete mathematics / Procedure for computing shortest distance| Discrete Mathematics

Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G.

  1. Initially, let P={a} and T=v-{a}. For every vertex t in T. Let ℓ (t) = w(a, t)
  2. Select the vertex in T that has the smallest index with respect to P. Let x denote the vertex.
  3. If x is the vertex wish to reach from a, stop.

If not, let P′=P∪{x} and T′=T-{x}. For every vertex t in T′, compute its index with respect to P′ according to ℓ ′(t) = Min[ℓ (t). ℓ (x)+w(x,t)]

  1. Repeat steps 2 and 3 using P′ as P and T′ as T.

In this procedure the necessary computation for keeping track of the path from a to x whose length is equal to ℓ (x) for each x in T. In that case we shall able to determine a shortest path from a to x as well as the shortest distance.

Problem: Apply the algorithm to determine a shortest path between a to z in the graph where the number associated with the edges are the distance between vertices.

Screenshot_21

Solution: Let P{a} and T = {b, c, d, e, z}. From the given figure we have using

ℓ (t)= w(a, t) relation

ℓ (b) = w(a, b) = 1

ℓ (c) = w(a, c) = 4

ℓ (d) = w(a, d) =∞

ℓ (b) = w(a, e) =∞

ℓ (b) = w(a, z) = ∞

Here ℓ (b) = w(a, b) = 1 is the smallest.

∴ x = 1.

So that P′ = P∪{x} = {a, b}

T′ = T – {x} = {c, d, e, z}

ℓ′ (t) denote the index of a vertex t in T′ with respect to P′. Then

 

ℓ′ (t) = Min[ℓ (t), ℓ(x)+w( x, t)]

 

ℓ′ (c) = Min [ℓ (c), ℓ(b)+w( b, c)] = Min [4, 1+2] = 3

 

ℓ′ (d) = Min [ℓ (d), ℓ (b) + w (b, d)] = Min [∞, 1+7] = 8

 

ℓ′ (e) = Min [ℓ (e), ℓ (b) + w (b, e)] = Min [∞, 1+5] = 6

 

ℓ′ (z) = Min [ℓ (z), ℓ(b) + w (b, z)] = Min [∞, 1+ ∞] = ∞

Here ℓ′ (c) = 3 is the smallest.

∴ x =c

So that P′ = {a, b, c}

T′ = T-{x} = {d, e, z}

Now we calculate

ℓ′ (d) = Min [ℓ (d), ℓ (c) + w (c, d)] = Min [8, 3+∞] = 8

 

ℓ′ (e) = Min [ℓ (e), ℓ (c) + w (c, e)] = Min [6, 3+1] = 4

 

ℓ′ (z) = Min [ℓ (z), ℓ(c) + w (c, z)] = Min [∞, 1+ ∞] = ∞

Here ℓ′ (e) = 4 is the smallest.

∴ x =e

So that P′ = {a, b, c, e}

T′ = T-{x} = {d, z}

Again we calculate

ℓ′ (d) = Min [ℓ (d), ℓ (e) + w (e, d)] = Min [8, 4+3] = 7

ℓ′ (z) = Min [ℓ (z), ℓ(e) + w (e, z)] = Min [∞, 4+ 6] = 10

Here ℓ′ (d) = 7 is the smallest.

∴ x =d

So that P′ = {a, b, c, e, d}

T′ = T-{x} = {z}

And ℓ′ (z) = Min [ℓ (z), ℓ(d) + w (d, z)] = Min [10, 7+ 2] = 9

Hence the required smallest or shortest distance is 9 from a to z and path is

{a, b, c, e, d, z}   (Answer).

Check Also

Euler’s formula for planner graphs| Discrete Mathematics

Proof: We have to proved V-E+R=2 for any connected planner graph. Where v, e, r ...

Leave a Reply

Your email address will not be published. Required fields are marked *