Comment by PrunJuice

One minor foible. Don't select edges that are part of the minimum path, instead remove edges that are not part of the minimum path until only the minimum path remains. This strategy works even on graphs with multiple minimum paths.