graph-theory - 如何确定两个节点是否连接？

Question

我担心这可能会解决NP-Complete问题。我希望有人可以给我一个答案，答案是否正确。我正在寻找的答案不仅仅是"is"或“不是”。我想知道为什么。如果您可以说:“这基本上是/不是NP完全的问题'x'。(维基百科链接)”

(不，这不是作业)

有没有一种方法可以确定两个点是否连接在任意非有向图上。例如，以下

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

点A到M(没有“I”)是可以打开或关闭的控制点(例如天然气管道中的阀门)。 “+”是节点(如管道T)，我想“井”和“房屋”也是节点。

我想知道是否关闭任意控制点(例如C)，井和房屋是否仍处于连接状态(其他控制点也可能关闭)。例如，如果B，K和D关闭，那么我们仍然有一条通过A-E-J-F-C-G-L-M的路径，而关闭C将断开水井和房屋的连接。当然;如果只是关闭D，则仅关闭C不会断开房屋。

另一种表达方式是C是桥/切边/地峡吗？

我可以将每个控制点都视为图表上的权重(打开时为0或关闭时为1)；然后找到Well和House之间的最短路径(结果> = 1表示它们已断开连接。我也可以通过多种方法来短路用于查找最短路径的算法(例如，一旦路径到达1，则丢弃该路径，然后停止一旦我们有了连接井和房屋等的任何路径，就可以进行搜索。)当然，我也可以对放弃之前要检查的跃点数设置一些人为的限制。

以前一定有人对这种问题进行过分类，我只是想念这个名字。

Answer 1

有关所有与图形相关的问题，请参见http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm，您的一站式服务。我相信您的问题实际上可以在二次时间内解决。