Introduction

Create a .java program that reads a directed weighted graph and returns a matrix of shortest paths from each node to every other node using the Floyd Warshall Algorithm.

Requirements

Download on your machine a java IDE NetBeans.

Start a new java project name it anything you want.

In the main method, declare two matrices, i.e. 2D arrays of size 5 x 5. One is for the graph, g, the other is for the intermediate nodes to be traversed, k.

Create a nested for loop that initializes g cells to 1000 and the diagonal cells to 0.

You are provided with two sample graphs in two different text files. Each file has three columns. First column is the source node, s, second column is the destination node, d, and the third column are the weight of the edge (s, d). Your program should read these numbers and populate the g matrix. For example,

1 5 1

2 1 4

the first line should set g[0][4] = 1 and the second line should set g[1][0] = 4. In order to read from a file you need to consider using a java class called Scanner.

Print the g matrix.

Use algorithm floyd2 on page 114 to create the shortest paths and intermediate nodes matrices. Hint: your g is D, and your k is P.

Print the g matrix again and the k matrix.