(5/5)

Assingment Description with output test cases provided as well as class notes.

1

THE FLOYD-WARSHALL ALGORITHM

• An intermediate vertex of a simple path p = {v1, v2, …, vq}

is any vertex of p other than vi

to vq

. i.e., any vertex in the set {v2, v3, …, vq-1}

For any pair of vertices i, j V,

we consider all paths from i to j whose intermediate vertices are

all drawn from {1, 2, …, k} k<= n = |V|

Let p be a minimum weight path among them.

2

Let p be a minimum weight path among them.

All intermediate vertices in {1,2,…k-1} All intermediate vertices in {1,2,…k-1}

i k j

P: All intermediate vertices in {1,2,…k}

p1 p2

3

•If k is not an intermediate vertex of path p,

then all intermediate vertices of path p are in the set {1,2,…,k-1}.

Thus a shortest path from vertex i to vertex j with all intermediate

vertices in the set {1,2,…,k-1} is also a shortest path from i to j.

with all intermediate vertices in the set {1,2,…,k}.

•If k is an intermediate vertex of path p.

then we break p down into

p1 is a shortest path from i to k with all intermediate vertices in the set

{1,2,…,k-1} and p2 is a shortest path from k to j with all

intermediate vertices in the set {1,2,…,k-1}.

k

j

i

p1 p2

4

A recursive solution to the all-pairs shortest-paths problem.

d (k)

ij : the weight of a shortest path from vertex i to vertex j with

all intermediate vertices in the set {1,2,…,k}

Recursive Definition:

d (k)

ij = w ij if k = 0

min (d (k-1)

ij, d (k-1)

ik + d (k-1) kj ) if k > 0

The matrix D (n) = (d (n)

ij ) gives the final answer.

i.e.,

d (n)

ij = (i, j) for all i, j V

because all intermediate vertices are in the set {1,2,…,n}

5

FLOYD-WARSHALL (W)

1 n=row[D]

2 let D (0) = W

3 for k=1 to n do

4 for i=1 to n do

5 for j=1 to n do

6 d (k)

ij = min (d (k-1)

ij, d (k-1)

ik + d (k-1) kj )

7 return D (n)

The running time: (n3

)

6

•Constructing s shortest path.

•Compute from D ---- O(n2

)

OR

•Compute “on-line” just as the Floyd-Warshall algorithm

compute the matrices D (n) :

(0)

ij = NIL if i = j or w ij =

i if i j and w ij <

For k 1

(k)

ij =

(k-1)

ij if d (k-1)

ij d (k-1)

ik + d (k-1) kj

(k-1) kj if d (k-1)

ij > d (k-1)

ik + d (k-1) kj

7

8 2 1 5 4 3 3 4

-4 6 7 8 1

-5 2

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Get Free Quote!

363 Experts Online