CODEWITHSUNDEEP
algorithmdata-structuresgraphdijkstra
Giorgi Tsertsvadze
Giorgi Tsertsvadze

Reputation: 433

The shortest path between nodes in graph

I don't know if I should be asking this here or not, the question is about algorithm. Imagine you have an undirected graph. Edges have different values. Imagine that some vertice are "good" and some are "bad". Now I want to determine two good nodes, so that path between them is shortest possible (if path include bad nodes that's not a problem).

Upvotes: 4

Views: 864

Answers (2)

btilly
btilly

Reputation: 46389

What you want to do is start growing paths from all good nodes at once, and then stop shortly after you find that two meet. Then you have found your shortest path.

There is a subtle complication. Consider a triangle ABC. If the weights of A-B and B-C are both 2, and A-C is 3, you look at the edges A-B and B-C before A-C. Which means that you find the path A-B-C (weight 4) before A-C (weight 3). However in all such cases you will have seen that the edge exists before you found the first one.

Here is pseudocode.

node_path_info is is a dictionary of vertex to information about the path
upcoming is priority queue of vertices to consider next, sorted on .cost

initialize node_path_info and upcoming
for node in list of good nodes:
    upcoming.add( {
        "node": node,
        "node_from": None,
        "cost": 0,
        "good_node", node,
    } )

best_path_cost = None
best_middle1 = None
best_middle2 = None
while upcoming:
    current = upcoming.pop()
    if current.node in good_node_from:
        if current.good_node == good_node_from[current.node]:
            pass # We found a loop
        else:
            cost = current.cost + node_path_info[current.node].cost
            if best_path_cost is None or cost < best_path_cost < best_path_cost:
                best_path_cost = cost
                best_middle1 = current.node
                best_middle1 = current.node_from
    else:
        node_path_info[current.node] = current
        if best_path_cost is not None: # still looking for first path
            for (next_node, weight) in get_connected_weight(current.node):
                upcoming.add({
                    "node": next_node,
                    "node_from": current.node,
                    "cost": current.cost + weight,
                    "good_node", current.good_node,
                })

path1 = path from best_middle1 back
path2 = path from best_middle2 back
path1 + reversed(path2) is your answer.

In the worst case you will need to visit all edges twice. With a random connected graph and 2 good nodes, you will visit all edges connected to O(sqrt(n)) vertices.

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33499

One approach is to add a source node that has a directed connection (with weight 0) to each good node.

Then run Dijkstra's algorithm to find the shortest path from the source node to every other node.

While running Dijkstra's algorithm, also keep track of which good node was the closest.

Then do a final pass over the edges A->B to find the cheapest value of "distance to good node from A" + "weight of edge" + "distance to good node from B", only including edges where the closest good node to A is not equal to the closest good node to B.

Upvotes: 0

Related Questions