THE FLOYD-WARSHALL ALGORITHM • An intermediate vertex of a simple path p = {v1, v2, …, vq}

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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