Algorithm Node A Connected to Node B in a graph

I am looking for an algorithm to test for a valid connection (shortest or longest) between two arbitrary nodes in a graph.

My graph is snapped to a grid with logical (x, y) coordinates with north / south / east / west connections, but the nodes can be randomly removed, so you can't assume that taking the edge with the coordinates closest to the target will always take you there.

The code is in python. The node data structure (object) has a list of connected nodes. The elements of the list are ref refs, so we can search that node list of the connected nodes list recursively, like this:

for pnode in self.connected_nodes:
    for cnode in pnode.connected_nodes:
        ...etc

      

        
        
        
      

    

I have included a diagram showing how the nodes display the x, y coordinates and how they relate north / east / south / west. Sometimes there are missing nodes (between J and K) and sometimes there are missing edges (between G and H). The presence of nodes and edges in the stream (although when we run the algorithm it takes a fixed snapshot in time) and it can only be determined by checking each node for it the list of connected nodes.

The algorithm should give a simple true / false about whether a valid connection exists between the two nodes. Recursion through each list of connected nodes blows up the number of operations required - if a node is n edges, no more than 4 ^ n operations are required. My understanding is something like Diistrika's algorithm, if you find the shortest path based on edge weights, but if there is no connection at all, will it still work?

For some background I am using this to model 2D destructible objects. Each node represents a piece of material, and if one or more nodes are out of touch with the rest of the material, then it should detach. In the diagram - D, H, R - should be away from the main body as they are not connected.

UPDATE:

While many of the answers posted may well work, DFS is fast, lightweight, and very appropriate. I am not fond of the idea of ​​glueing extra edges between nodes with high weights to use Dijkstra, because the node itself may disappear as well as the edges. The SSC method seems to be more suitable for distinguishing between strong and loosely coupled plots, which in my plot will work if there is one edge between G and H.

Here is my experiment code for DFS search that creates the same graph as the chart.

class node(object):
    def __init__(self, id):
        self.connected_nodes  = []
        self.id               = id

    def dfs_is_connected(self, node):
        # Initialise our stack and our discovered list
        stack      = []
        discovered = []

        # Declare operations count to track how many iterations it took
        op_count = 0

        # Push this node to the stack, for our starting point
        stack.append(self)

        # Keeping iterating while the stack isn't empty
        while stack:
            # Pop top element off the stack
            current_node = stack.pop()

            # Is this the droid/node you are looking for?
            if current_node.id == node.id:
                # Stop!
                return True, op_count

            # Check if current node has not been discovered
            if current_node not in discovered:

                # Increment op count
                op_count += 1

                # Is this the droid/node you are looking for?
                if current_node.id == node.id:
                    # Stop!
                    return True, op_count

                # Put this node in the discovered list
                discovered.append(current_node)

                # Iterate through all connected nodes of the current node
                for connected_node in current_node.connected_nodes:
                    # Push this connected node into the stack
                    stack.append(connected_node)

        # Couldn't find the node, return false. Sorry bud
        return False, op_count


if __name__ == "__main__":

    # Initialise all nodes
    a = node('a')
    b = node('b')
    c = node('c')
    d = node('d')
    e = node('e')
    f = node('f')
    g = node('g')
    h = node('h')
    j = node('j')
    k = node('k')
    l = node('l')
    m = node('m')
    n = node('n')
    p = node('p')
    q = node('q')
    r = node('r')
    s = node('s')

    # Connect up nodes
    a.connected_nodes.extend([b, e])
    b.connected_nodes.extend([a, f, c])
    c.connected_nodes.extend([b, g])
    d.connected_nodes.extend([r])
    e.connected_nodes.extend([a, f, j])
    f.connected_nodes.extend([e, b, g])
    g.connected_nodes.extend([c, f, k])
    h.connected_nodes.extend([r])
    j.connected_nodes.extend([e, l])
    k.connected_nodes.extend([g, n])
    l.connected_nodes.extend([j, m, s])
    m.connected_nodes.extend([l, p, n])
    n.connected_nodes.extend([k, m, q])
    p.connected_nodes.extend([s, m, q])
    q.connected_nodes.extend([p, n])
    r.connected_nodes.extend([h, d])
    s.connected_nodes.extend([l, p])

    # Check if a is connected to q
    print a.dfs_is_connected(q)
    print a.dfs_is_connected(d)
    print p.dfs_is_connected(h)