Shortest path (deriving)

A graph G contains n vertices {1, 2, ... n} and is represented by its adjacency matrix, A.
Write code to transform A, such that, A[i, j] is the shortest path from vertex i, to vertex j.

Given that n = 4 and A is
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

derive the matrix of shortest paths, showing the matrix after each of the 4 major steps.

Solution

for k = 1 to n
for i = 1 to n
for j=1 to n
A[i, j] = min(A[i, j], A[i, k] + A[k, j]) [2 marks]

A:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

k=1:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 7 0

k=2:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 12
3 ∞ 7 0

k=3:
0 ∞ 4 16
∞ 0 ∞ 7
18 5 0 ∞
3 12 9 0

k=4:
0 ∞ 4 16
10 0 14 7
18 5 0 ∞
3 12 9 0

[5 marks]

Maximum-sum contiguous subvector

Question

Given an array A[1..n] of n real numbers, write programming code which implements an O(n)-time algorithm for finding the maximum-sum contiguous subvector. For example, in the array
{11, -21, 39, 6, -33, 38, 77, -73, -3, 64}
the maximum sum (122) is obtained by summing the third through seventh elements; your code should print 122 3 7.

Solution

Maximum sum in any contiguous subvector
/* Precondition: x[1..n] is an array of floating-point (real) numbers. */
procedure MaxSumContigVector (x[1..n]: float)

// Returns the maximum sum of a continuous subarray drawn from x.

MaxSoFar := 0.0

MaxEndingHere := 0

i := 1

while i ≠ n + 1 do

MaxEndingHere := max(0.0, MaxEndingHere + x[i])

MaxSoFar := max(MaxSoFar, MaxEndingHere)

i := i + 1

end

return MaxSoFar

source:
http://www.cse.sc.edu/~mgv/csce350sp04/lectureNotes/maxsumcontigvector.html