How to determine if two nodes are connected?

See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , your one stop shop for all graph related problems. I believe your problem is in fact solvable in quadratic time.

You don't need Dijkstra's algorithm for this problem, as it uses a Heap which isn't needed and introduces a factor of log(N) to your complexity. This is just breadth first search - don't include the closed edges as edges.

Your description seems to indicate that you are just interested in whether two nodes are connected, not finding the shortest path.

Finding if two nodes are connected is relatively easy:

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.

If you use a hash table or something similar for toDoSet and doneSet, I believe this is a linear algorithm.

Note that this algorithm is basically the mark portion of mark-and-sweep garbage collection.