Как определить, соединены ли два узла?

Ваше описание, кажется, указывает, что Вы просто интересуетесь тем, соединены ли два узла, не найдя кратчайший путь.

Открытие, если два узла соединены, относительно легко:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoSet
  Add it to doneSet
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

, Если Вы используете хэш-таблицу или что-то подобное для toDoSet и doneSet, я полагаю, что это - линейный алгоритм.

Примечание, что этот алгоритм является в основном частью метки сборки "мусора" метки-и-развертки.

Вам не нужен алгоритм Dijkstra для этой проблемы, поскольку это использует "кучу", которая не необходима и представляет фактор журнала (N) к Вашей сложности. Это - просто поиск в ширину - не включают закрытые края как края.

Проблема нахождения кратчайшего пути не полна NP. Это назвало проблему Кратчайшего пути (первоначально достаточно) и существует алгоритмы для решения многих различных изменений его.

проблема определения, если два узла соединены, не полна NP также. Можно использовать поиск в глубину, начинающий в любом узле определить, подключен ли он к другому узлу.

не полный NP, решенный с известным решением - Алгоритм Dijkstra

Мне кажется, что Вы идете к решению, но возможно, что я неправильно понял проблему. Если Вам действительно нравитесь Вы, говорят и дают закрытые края 1 как вес, можно просто применить алгоритм Dijkstra, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . Это должно решить Вашу проблему в O (E*lg(V))

Предположение, что у Вас есть матрица смежности:

bool[,] adj = new bool[n, n];

, Где bool [я, j] = верный, если существует открытый контур между мной и j и bool [я, я] = ложь.

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

Вот рекурсивная версия алгоритма выше (записана в Ruby):

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end

Dijkstra является излишеством!! Просто используйте поиск в ширину от для поиска узла, которого Вы хотите достигнуть. Если Вы не можете найти его, это не соединено. Сложность является O (nm) для каждого поиска, который является меньше тогда Dijkstra.

Несколько связанный max-flow/min-cut проблема. Ищите его, это могло бы относиться к Вашей проблеме.