# APPENDIX A

The following Fortran subroutine implements the Viterbi algorithm:

```	subroutine rviterbi(n1,n2,npath,in,out,qqsum,qqmin)
c
c  ------------------------------------
c		find the shortest-path with viterbi algorithm
c  ------------------------------------
c
c	n1,n2				dimension of the array
c	npath				number of allowed paths
c	in				input array
c	qqsum,qqmin			auxiliary array
c	out				output array
c
c  ------------------------------------
c
implicit none

integer n1,n2,i1,i2
integer npath,ipath
integer i2min,i2max,npathh,ipathmin,ipathmax
integer i2pick,i2newpick
real minvalue
real in(n1,n2)
real qqsum(n1,n2),qqmin(n2)
real out(n1)

npathh = (npath-1)/2
c VITERBI ALGORITHM
c    forward error accumulation
call zero(n2,qqmin)
call zero(n1*n2,qqsum)
do i2 = 1,n2
qqsum(1,i2) = in(1,i2)
enddo
do i1 = 2,n1
do i2 = 1,n2
qqmin(i2) = 1.e+30
enddo
do ipath = -npathh,npathh
i2min = max(1,1-ipath)
i2max = min(n2,n2-ipath)
do i2 = i2min,i2max
qqmin(i2) = min(qqmin(i2),qqsum(i1-1,i2+ipath))
enddo
enddo
do i2 = 1,n2
qqsum(i1,i2) = qqmin(i2)+in(i1,i2)
enddo
enddo

c    backward tracing
i1 = n1
i2pick = (n2-1)/2
minvalue = qqsum(i1,i2pick)
do i2 = 1,n2
if(qqsum(i1,i2) .lt. minvalue)then
i2pick = i2
minvalue = qqsum(i1,i2pick)
endif
enddo
out(i1) = real(i2pick)
do i1 = n1-1,1,-1
minvalue = 1.e+30
if(qqsum(i1,i2pick) .le. minvalue)then
minvalue = qqsum(i1,i2pick)
i2newpick = i2pick
endif
ipathmin = max(-npathh,1-i2pick)
do ipath = ipathmin,-1
if(qqsum(i1,i2pick+ipath) .lt. minvalue)then
minvalue = qqsum(i1,i2pick+ipath)
i2newpick = i2pick+ipath
endif
enddo
ipathmax = min(npathh,n2-i2pick)
do ipath = 1,ipathmax
if(qqsum(i1,i2pick+ipath) .lt. minvalue)then
minvalue = qqsum(i1,i2pick+ipath)
i2newpick = i2pick+ipath
endif
enddo
i2pick = i2newpick
out(i1) = real(i2pick)
enddo

return
end
```