# Are all public roads interconnected?

**URL:** <https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403>\
**Category:** Factual Questions\
**Created:** [August 14, 2009, 2:26pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403 "2009-08-14T14:26:24Z")\
**Posts on this page:** 11\
**Page:** 3

<div class="post-metadata">

**Author:** ![Uncertain](https://avatars.discourse-cdn.com/v4/letter/u/6a8cbe/32.png) [@Uncertain](https://boards.straightdope.com/u/Uncertain)\
**Post date:** [August 15, 2009, 5:48am UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/41 "2009-08-15T05:48:21Z")

</div>

> [@gazpacho](#):
>
> If you think of the roads as the nodes and the intersections as paths it becomes the same problem. I would be interested in hearing how you think it is simpler problem.

In TSP you can only visit each node once, right? You can visit each road (segment of road, really) as many times as you like (there is likely no way to do it without visiting some more than once).

The costs in TSP are associated with the paths. In the driving problem they’re associated with the road segments, so I don’t see how it works if the intersections are the paths.

---

<div class="post-metadata">

**Author:** ![gazpacho](https://avatars.discourse-cdn.com/v4/letter/g/6f9a4e/32.png) [@gazpacho](https://boards.straightdope.com/u/gazpacho)\
**Post date:** [August 15, 2009, 6:00am UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/42 "2009-08-15T06:00:23Z")

</div>

> [@Uncertain](#):
>
> In TSP you can only visit each node once, right? You can visit each road (segment of road, really) as many times as you like (there is likely no way to do it without visiting some more than once).
> 
> The costs in TSP are associated with the paths. In the driving problem they’re associated with the road segments, so I don’t see how it works if the intersections are the paths.

As I remember the TSP. It is the shortest path visiting each city at least once. I think you can map the length of roads onto new connections between each node.

I don’t want to hijack this thread more than I have already. If people are interested in this topic open let me know and we can open a new thread.

---

<div class="post-metadata">

**Author:** ![NineToTheSky](https://avatars.discourse-cdn.com/v4/letter/n/b5a626/32.png) [@NineToTheSky](https://boards.straightdope.com/u/NineToTheSky)\
**Post date:** [August 15, 2009, 6:14am UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/43 "2009-08-15T06:14:46Z")

</div>

> [@Colibri](#):
>
> Actually, the guy who completed the most recent trip did drive all the way. It took him three years, though. He would drive only during the three month dry season, leaving the car in someone’s care during the rainy season until he could come back the next year. And by “winching” I mean winching the car up steep slopes with a cable and a winch attached to the front of the vehicle. I don’t think this is cheating, since you are using the car’s own engine to move it along.
> 
> Interesting article, although a little over the top in places. I know almost all the people mentioned in the article. I’ve been to the Darien several dozen times, and have led expeditions into some of the more remote and unexplored mountain ranges. It’s amazing that a wilderness like that still can exist in a country as small as Panama.

I’m going away for the weekend (in a few minutes, so this has got to be quick), so I’ll be computerless today and tomorrow, but I’d love to hear more of your travels. I had no idea you are an intrepid explorer. Maybe I’ll start a tell us about interesting journeys thread.

---

<div class="post-metadata">

**Author:** ![dtilque](https://avatars.discourse-cdn.com/v4/letter/d/d6d6ee/32.png) [@dtilque](https://boards.straightdope.com/u/dtilque)\
**Post date:** [August 15, 2009, 9:06am UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/44 "2009-08-15T09:06:07Z")

</div>

> [@Giles](#):
>
> In addition, the roads on Point Roberts in Washington State can only be reached by driving outside the United States and through two border control points.

At the other end of the US-Canadian border is a complementary situation. [Campobello Island](http://en.wikipedia.org/wiki/Campobello_Island), New Brunswick can be reached by a bridge from Lubec ME, but there’s no bridge from the New Brunswick mainland. A Canadian wanting to drive there (without taking a ferry) has to go through the US.

> [@Sunspace](#):
>
> There are a number of communities in Northern Ontario that are connected only by railway to “the South”. Are there similar in the Lower 48?

As far as I know, there are none. If there are any, they are quite small and located in remote mountainous areas, such as the Rockies, the Sierras, or the Cascades.

BTW, Churchill MB is also only connected by railway and not by road.

Well known trivium that I’m surprised no one has brought up: Juneau AK is the largest city on the North American mainland not connected to the highway grid.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [August 15, 2009, 1:03pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/45 "2009-08-15T13:03:20Z")

</div>

> [@gazpacho](#):
>
> As I remember the TSP. It is the shortest path visiting each city at least once. I think you can map the length of roads onto new connections between each node.

TSP means _exactly_ once for each node. Crossing each edge once is an Eulerian path/tour and is very easy to test for. (The “hardest” part is testing if the graph is connected. Shades of the OP.) There are Wikipedia articles on those of course.

---

<div class="post-metadata">

**Author:** ![Uncertain](https://avatars.discourse-cdn.com/v4/letter/u/6a8cbe/32.png) [@Uncertain](https://boards.straightdope.com/u/Uncertain)\
**Post date:** [August 15, 2009, 2:03pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/46 "2009-08-15T14:03:49Z")

</div>

> [@ftg](#):
>
> TSP means _exactly_ once for each node. Crossing each edge once is an Eulerian path/tour and is very easy to test for. (The “hardest” part is testing if the graph is connected. Shades of the OP.) There are Wikipedia articles on those of course.

But a Eulerian path crosses each edge _exactly_ once, right? So it doesn’t apply either. And is it easy to find the shortest such path, or just to determine the existence of one?

---

<div class="post-metadata">

**Author:** ![Heart\_of\_Dorkness](https://avatars.discourse-cdn.com/v4/letter/h/4bbf92/32.png) [@Heart\_of\_Dorkness](https://boards.straightdope.com/u/Heart_of_Dorkness)\
**Post date:** [August 15, 2009, 2:32pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/47 "2009-08-15T14:32:38Z")

</div>

> [@Uncertain](#):
>
> But a Eulerian path crosses each edge _exactly_ once, right? So it doesn’t apply either. And is it easy to find the shortest such path, or just to determine the existence of one?

Every path that crosses each edge exactly once will be, by definition, exactly as long as every other such path. So there is no “shortest” such path. And yes, the [way to determine the existence of an Euler path](http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg) is easy.

---

<div class="post-metadata">

**Author:** ![Polycarp](https://avatars.discourse-cdn.com/v4/letter/p/82dd89/32.png) [@Polycarp](https://boards.straightdope.com/u/Polycarp)\
**Post date:** [August 15, 2009, 4:35pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/48 "2009-08-15T16:35:04Z")

</div>

In addition to both Nome and Juneau in Alaska – both of which have a road system connecting them to outlying settlements and isolated dwellings, but which are not connected by road to the rest of the American-Canadian-Mexican road system – there are no doubt small mountainous areas with roads not linked to the main grid within the “Lower 48”). The one I’m aware of is [here](http://maps.google.com/maps?f=q&source=s_q&hl=en&q=Number+4,+Hamilton,+New+York+12847&sll=37.0625,-95.677068&sspn=31.839416,56.513672&ie=UTF8&cd=1&geocode=FTyzoAIdz4OP-w&split=0&ll=43.896408,-74.981346&spn=0.11306,0.220757&z=12). At the scale the map is at, you will see roads as pale brownish lines on either side of the southwest part of Stillwater Reservoir. Zoom in (+) and move east and west of the water (\>) and (\<) to get clearer detail. The Number Four-Big Moose Road west of the reservoir is an integral part of the North American grid, connecting Lowville and Old Forge, New York by a dirt road that is (barely) drivable by normal two-wheel-drive vehicles; Barb and I traveled it once. But east of the reservoir’s southwest embayment, running along the southern shore of the eastern arm of the reservoir, is a road leading over to “Little Rapids” and “Beaver River”, the latter a hamlet. Its sole connection to the outside world is the Adirondack Railway track running through it; cars are brought in (rarely) via rail or by boat across the reservoir. And that road along the south shore east of the embayment has no road connection to anywhere else in the U.S. As I understand it, nobody registers their cars in there, since the only roads are all privately owned. I haven’t been there (to Beaver River) myself, but it was the subject of a story in a local newspaper years back.

---

<div class="post-metadata">

**Author:** ![jasonh300](https://avatars.discourse-cdn.com/v4/letter/j/46a35a/32.png) [@jasonh300](https://boards.straightdope.com/u/jasonh300)\
**Post date:** [August 15, 2009, 5:01pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/49 "2009-08-15T17:01:01Z")

</div>

> [@LouisB](#):
>
> There are parts of some streets in St. Petersburg, FL that have brick surfaces; some of them are fairly rough and I wouldn’t count them as paved. Historical yes but only marginally drivable, IMHO.

They’re paved with bricks. In Louisiana, we have interstate highways with rougher surfaces than those brick roads, and they still consider them to be “paved”. :smack:

---

<div class="post-metadata">

**Author:** ![Colibri](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/colibri/32/1841_2.png) [@Colibri](https://boards.straightdope.com/u/Colibri)\
**Post date:** [August 15, 2009, 5:06pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/50 "2009-08-15T17:06:30Z")

</div>

> [@NineToTheSky](#):
>
> I’m going away for the weekend (in a few minutes, so this has got to be quick), so I’ll be computerless today and tomorrow, but I’d love to hear more of your travels. I had no idea you are an intrepid explorer. Maybe I’ll start a tell us about interesting journeys thread.

I’d be happy to.

---

<div class="post-metadata">

**Author:** ![Uncertain](https://avatars.discourse-cdn.com/v4/letter/u/6a8cbe/32.png) [@Uncertain](https://boards.straightdope.com/u/Uncertain)\
**Post date:** [August 15, 2009, 8:41pm UTC](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403/51 "2009-08-15T20:41:00Z")

</div>

> [@Heart\_of\_Dorkness](#):
>
> Every path that crosses each edge exactly once will be, by definition, exactly as long as every other such path. So there is no “shortest” such path. And yes, the [way to determine the existence of an Euler path](http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg) is easy.

OK, but the road thing doesn’t require crossing each edge exactly once. In fact I can assure you, based on the streets down the block from me, that there is no Eulerian path (even among the main set of interconnected roads). Finding the shortest path that crosses each edge at least once is a different problem, and might be much harder, especially when the edges are weighted.

[Previous page](https://boards.straightdope.com/t/are-all-public-roads-interconnected/506403.md?page=2)