From: Wang Zirui [wangziru@comp.nus.edu.sg]
Sent: Friday, 20 February, 2004 1:26 PM
To: Leong Hon Wai
Subject: Longest Simple Path

Dear Prof. Leong,

Below is my solution to the homework problem.

	Variables
		adj[][]: adjacent list
		w[][]: weight of edges
		s: starting vertex
		t: ending vertex

		max: maximum length from s to t
		p[]: array of parent vertices

		u: current vertex
		d: distance covered so far
		o[]: boolean array storing if a vertex is on current path

	Longest-Simple-Path(s, t)
	  if s == t
	    max = 0
	  else max = -inf
	  o[s] = false
	  for each vertex u in adj[s]
	    p[u] = s
	    DFS(u, w[s][u])
	  return max, p[]

	DFS(u, d)
	  if u == t
	    if d > max
	      max = d
	      store p[] if necessary
	  else
	    o[u] = true
	    for each vertex v in adj[u]
	      if o[v] == false
	        p[v] = u
	        DFS(v, d + w[u][v])
	    o[u] = false

EXPLANATION

Since this problem is NP-complete, there is no known faster solution than
enumerating all possible paths from s to t. We have to search exhaustively
using DFS.

A simple path is required, thus I use the boolean array o[] to avoid going
to one vertex twice. Upon reaching destination t, I compare the distance
covered so far with current maxmium length and update the maximum if
necessary.

The case where s is identical to t needs separate treatment, since the
lowest bound is 0 now, i.e. just staying at s.

CLAIM The algorithm is correct.

PROOF

Assume it is wrong. There is a path that is strictly longer than the
returned path. Suppose the first vertex on the longer path that differs
from the returned path is v. Then v cannot be s since s is common; so v
has a parent vertex u that lies on the initial shared path. But in DFS(),
every vertex reachable from u is considered; so v has also been
considered.

Similarly, DFS() has reached all the vertices on the longer path after v
in the same order. In other words, the longer path has been explored. So
its length has been compared with max, and the larger of the two has been
stored. This contradicts the assumption that the length of the longer path
is strictly greater than the stored maximum value. The claim is proven. #

Sincerely,
Wang Zirui