[1] http://en.wikipedia.org/wiki/Cognitive_map
[2] http://www.muskingum.edu/~psych/psycweb/history/tolman.htm#T...
BTW, I notice, in the WP article:
> In a review by Bennett[8] it is argued that there are no clear evidence for cognitive maps in non-human animals (i.e. cognitive map according to Tolman's definition). This argument is based on analyses of studies where it has been found that simpler explanations can account for experimental results.
Once they've used the subway a few times, they probably learn to distinguish the sounds and smells of the stops they're interested in. Even if they can't read or understand spoken announcements, most dogs seem to figure out what vehicles are for without much trouble.
Once one or more dogs have learned this trick, transfer of information kicks in. At the end of the day, the other dogs at the shelter can probably tell who ate well that day, and they're likely to want to go with that dog to see where the food is at. The subway dog may even encourage his friends to come along; most of us have probably seen and understood a dog's "hey come with me and see this thing" signals, and dogs are pack animals.
Smell fresh meat/produce, get off in Chinatown.
Smell the sea, get off by the river, etc..