As per comments, OP's concepts of "right/correct" aren't helpful here. Lots of prepositions are valid, depending on context. Here are some estimates from Google Books for he walked xxxx the road... down:18100 along:15400 up:8020 on:7700 across:5710 into:663 over:437 in:5
I immediately recognise a problem with those figures - as a native speaker, I know perfectly well that on, for example, isn't particularly common for that particular search text. But estimates in GB are skewed according to how often various subsections of the text occur anywhere in the corpus (walked on, on the, on the road, etc.). Here are the values after scrolling through to establish how many actual instances occur...
Obviously across, over are used in the context of getting from one side of the road to the other, and into for stepping off the sidewalk on to the tarmac traffic surface. In the context of using the road to get somewhere by foot, we normally use along, down, up.
I don't think it's worth differentiating between on, in. Almost every actual instance is equivalent with either, and usually would be better replaced by along, down, up.