You either shrink picture horizontally by one pixel or vertically by one pixel; seams must be 8-connected and always advance by 1 pixel in the opposite direction to the one being removed. It's a heuristics and by making it that way you can guarantee exactness of 1px removal.
These days it's a popular algorithm to be implemented as a midterm project in computational photography courses at top schools.
Well, think about what it would mean to remove a seam diagonally: the edges of the picture would no longer line up. The only way to avoid this is to always remove a seam along one of the axes at a time.
Just run the algorithm twice?
Better yet, scale the image proportionally down to the largest of the two target sides, then run the algorithm once in the direction that needs to shrink.