SUNY Geneseo Department of Computer Science

Problem Set 9—The Floyd-Warshall Algorithm

CSci 242, Spring 2013

Prof. Doug Baldwin

Due Thursday, March 28

Purpose

This exercise deepens your understanding of the Floyd-Warshall all-pairs shortest path algorithm, and of its connection to dynamic programming.

Background

The Floyd-Warshall algorithm is a dynamic programming algorithm for efficiently finding the least-cost paths between every pair of vertices in a graph. It is presented in section 25.2 of our textbook, and we discussed it in lecture on March 26.

Exercise

Solve each of the following problems.

Problem 1

Exercise 25-2.6 in the textbook.

Problem 2

Explain why the Floyd-Warshall algorithm should have an invariant that for all i and j, d_kj^k = d_kj^k-1 and d_ik^k = d_ik^k-1. (It does, in fact, have this invariant.)

Problem 3

Problem 15-1 in the textbook.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Schedule your meeting to last 15 minutes. Please sign up for your meeting on the schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. Be sure your meeting ends by the end of the day on the due date above.