An AMPL Implementation of the Floyd-Warshall Algorithm

The following is an example of how to use the run file fw_solve.txt to run the Floyd-Warshall algorithm on a network represented in the format described by the AMPL model file mcnfp_model.txt. This example uses the Unix operating system and the commands that user types are in bold, italic type. The data file for this example is fw1_data.txt.

% ampl < fw_solve.txt

Shortest Path Distances:
From    To      dist    pred
1       1       0       0
1       2       6       3
1       3       5       4
1       4       2       1
2       1       8       3
2       2       0       0
2       3       7       4
2       4       4       2
3       1       1       3
3       2       1       3
3       3       0       0
3       4       3       1
4       1       4       3
4       2       4       3
4       3       3       4
4       4       0       0

If there are no negative-cost cycles in the network, then the program prints outs list of shortest-path distances and predecessors for all node pairs. It also saves this data in AMPL format to a file called fw.out.

% more fw.out
param: d :=
1 1   0
1 2   6
1 3   5
1 4   2
2 1   8
2 2   0
2 3   7
2 4   4
3 1   1
3 2   1
3 3   0
3 4   3
4 1   4
4 2   4
4 3   3
4 4   0
;

param:  pred :=
1 1   0
1 2   3
1 3   4
1 4   1
2 1   3
2 2   0
2 3   4
2 4   2
3 1   3
3 2   3
3 3   0
3 4   1
4 1   3
4 2   3
4 3   4
4 4   0
;

A second run file called fw_show_path.txt uses fw.out to find the arcs in a shortest path between a user-specified source and sink node. In this example the source is node 1 and sink is node 2.

% ampl < fw_show_path.txt
set NODES_IN_PATH := 2 3 4 1;

d[1,2] = 6.
From 1 to 4: cost = 2
From 4 to 3: cost = 3
From 3 to 2: cost = 1

Here's what happens when we change the data file in fw_solve.txt from fw1_data.txt to fw2_data.txt (which contains a negative-cost cycle):

% cat fw2_data.txt
# Data for the maximizing-rent example given in class

set NODES := 1 2 3 4; 
set ARCS := (1,4) (2,1) (2,3) (4,3) (4,2); 

param:  c :=    
1 4 1
2 1 2
2 3 1
4 2 -4
4 3 3;


% ampl < fw_solve.txt
Negative-Cost Cycle Found:
Arc (1,4) has cost 1
Arc (2,1) has cost 2
Arc (4,2) has cost -4