Notes:Diff algorithm

Example paths

$\begin{xy} \xymatrix{ \ & 0 & \mathrm{a} & \mathrm{b} & \mathrm{c} & \mathrm{a} & \mathrm{b} & \mathrm{b} & \mathrm{a} & \mathrm{c} \\ 0 & \text{S} \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[d] \ar[r] & \cdot \ar[d] \\ \mathrm{a} & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[d] \ar[r] & \cdot \ar[d]\\ \mathrm{b} & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[d] \ar[r] & \cdot \ar[d]\\ \mathrm{b} & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[d] \ar[r] & \cdot \ar[d]\\ \mathrm{a} & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[r] \ar[d] & \cdot \ar[d] \ar[r] & \cdot \ar[d]\\ \mathrm{b} & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \cdot \ar[r] & \times & } % the chains \ar@{->} "2,2";"3,3" \ar@{->} "3,3";"4,4" \ar@{->} "4,3";"5,4" \ar@{->} "5,2";"6,3" \ar@{->} "6,3";"7,4" % first 2 cols done \ar@{->} "5,5";"6,6" \ar@{->} "6,6";"7,7" \ar@{->} "6,7";"7,8" % bottom 2-chain and 1 chain done \ar@{->} "2,5";"3,6" \ar@{->} "3,6";"4,7" \ar@{->} "4,7";"5,8" \ar@{->} "5,8";"6,9" % 4 chain done! \ar@{->} "4,6";"5,7" \ar@{->} "2,8";"3,9" \ar@{->} "3,7";"4,8" % and the 3 that go / through the 4 chain (the bottom right already being a part of a 2 chain %START OF RED PATH \ar@[red]@/^/@{->} "2,2";"2,3" \ar@[red]@/^/@{->} "2,3";"2,4" \ar@[red]@/^/@{->} "2,4";"2,5" \ar@[red]@/^/@{->} "2,5";"2,6" \ar@[red]@/^/@{->} "2,6";"2,7" \ar@[red]@/^/@{->} "2,7";"2,8" \ar@[red]@/^/@{->} "2,8";"2,9" \ar@[red]@/^/@{->} "2,9";"2,10" %and down \ar@[red]@/^/@{->} "2,10";"3,10" \ar@[red]@/^/@{->} "3,10";"4,10" \ar@[red]@/^/@{->} "4,10";"5,10" \ar@[red]@/^/@{->} "5,10";"6,10" \ar@[red]@/^/@{->} "6,10";"7,10" %start of green path \ar@[green]@/_/@{->} "2,2";"2,3" \ar@[green]@/_/@{->} "2,3";"2,4" \ar@[green]@/_/@{->} "2,4";"2,5" %now go down the 4-chain \ar@[green]@/_/@{->} "2,5";"3,6" \ar@[green]@/_/@{->} "3,6";"4,7" \ar@[green]@/_/@{->} "4,7";"5,8" \ar@[green]@/_/@{->} "5,8";"6,9" %now down and across \ar@[green]@/^/@{->} "6,9";"7,9" \ar@[green]@/^/@{->} "7,9";"7,10" \end{xy}$

Example shortest paths