CODEWITHSUNDEEP
algorithmoptimizationgraphshortest-path
AlexC75
AlexC75

Reputation: 51

Shortest path from one source which goes through N edges

In my economics research I am currently dealing with a specific shortest path problem:

Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from one source S, which goes through N edges. The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.

Is there an efficient algorithm for this problem?

Upvotes: 5

Views: 710

Answers (2)

jacobm
jacobm

Reputation: 14025

The "exactly N edges" constraint makes this problem much easier to solve than if that constraint didn't exist. Essentially you can solve N = 0 (just the start node), use that to solve N = 1 (all the neighbors of the start node), then N = 2 (neighbors of the solution to N = 1, taking the lowest cost path for nodes that are are connected to multiple nodes), etc.

In pseudocode (using {field: val} to mean "a record with a field named field with value val"):

# returns a map from node to cost, where each key represents 
# a node reachable from start_node in exactly n steps, and the
# associated value is the total cost of the cheapest path to 
# that node
cheapest_path(n, start_node):
  i = 0
  horizon = new map()
  horizon[start_node] = {cost: 0, path: []}
  while i <= n:
    next_horizon = new map()
    for node, entry in key_value_pairs(horizon):
      for neighbor in neighbors(node):
        this_neighbor_cost = entry.cost + edge_weight(node, neighbor, i)
        this_neighbor_path = entry.path + [neighbor]
        if next_horizon[neighbor] does not exist or this_neighbor_cost < next_horizon[neighbor].cost:
          next_horizon[neighbor] = {cost: this_neighbor_cost, path: this_neighbor_path}
    i = i + 1
    horizon = next_horizon
  return horizon

We take account of dynamic weights using edge_weight(node, neighbor, i), meaning "the cost of going from node to neighbor at time step i.

This is a degenerate version of a single-source shortest-path algorithm like Dijkstra's Algorithm, but it's much simpler because we know we must walk exactly N steps so we don't need to worry about getting stuck in negative-weight cycles, or longer paths with cheaper weights, or anything like that.

Upvotes: 0

Hans Olsson
Hans Olsson

Reputation: 12507

One possibility would be:

First find the lowest edge-weight in the graph.

And then build a priority queue of all paths from the starting edge (initially an empty path from starting point) where all yet-to-be-handled edges are counted as having the lowest weight.

Main loop:

  1. Remove path with lowest weight from the queue.
  2. If path has N edges you are done
  3. Otherwise add all possible one-edge extensions of that path to priority queue

However, that simple algorithm has a flaw - you might re-visit a vertex multiple times as i:th edge (visiting as 2nd and 4th is ok, but 4th in two different paths is the issue), which is inefficient.

The algorithm can be improved by skipping them in the 3rd step above, since the priority queue guarantees that the first partial path to the vertex had the lowest weight-sum to that vertex, and the rest of the path does not depend on how you reached the vertex (since edges and vertices can be duplicated).

Upvotes: 1

Related Questions