CS209 lab3

CS209 lab3

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l3.html

For this lab you should submit all source code (python files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code).
The above material should be uploaded to BLACKBOARD before the deadline of midnight Thursday 15th. February 2018. You will lose 20% for each day (or part of day) the lab is late.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students _v4.pdf. You risk getting zero for your lab if it is found to be plagiarized.

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/
Consider the Floyd "all pairs shortest path" algorithm described in lectures. This finds the shortest route on a labelled graph (network) between any two vertices (points).

Write the Floyd algorithm in PYTHON, using lists (of lists...) to store the necessary matrices.

Run your program on the data given at http://www.maths.nuigalway.ie/~gettrick/teach/cs209/nums.txt. Hence, state the shortest distance between nodes

3 and 15
4 and 6
17 and 19

(For this part - we are not worried about how to read in the data - you can read it in from a file, from the user, or just "hard wire" it in to the program.) Note: Instead of the "infinity" talked about in lectures, or the "zero" in the actual data, corresponding to points that are not connected, do the following. Assume the data is, as given, with 0 in positions where i and j are not directly connected. To "mimic" infinity, your program should put in a large positive number in this position. More precisely: that large positive number can be just (sum of all the non-zero entries of the matrix)+1, to guarantee it will be bigger than the other entries. Do this calculation and replacement in PYTHON. (Example - were the matrix [[0,0,2],[0,0,5],[2,5,0]] we would replace the zeros by 15 = 2+5+2+5+1).

Adapt your program as follows:

For each matrix - do not store n x n numbers: Since the matrix is always symmetric, store just the diagonal and upper triangular part. [Hint - if the data type is a list (L) of lists, then element j of L can be just a list of (n-j) numbers].
For the recursion D_ij^k = min( D_ij^k-1, D_ik^k-1 + D_kj^k-1), make sure that in the cases where k=i or k=j, you do not calculate min( D_ij^k-1, D_ik^k-1 + D_kj^k-1). In these cases, just assign D_ij^k = D_ij^k-1.

Submit your new program.