When travelling down a hallway with few people going different ways, I sometimes come across someone who travels down the same side of the hall in a different direction from me. When I go to move around them, they do too, creating a dance to get around each other, exactly like the Harry Potter and the Goblet of Fire, when he asks Cho to the ball.
This is always awkward, and causes me to apologize for being in the way, which always makes me feel like it's my fault for being in their way (other issues cause this). In some cases, this dance goes on until (like in the movie) someone uses physical contact to move both parties in their respective directions around each other. In many environments, this may be seen as rude or too forward to make physical contact, so I don't really know how to handle myself.
How can I avoid the inevitable stutter step that happens when people travel different directions in a hallway?