CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdijkstranp-hard
CSDUG
CSDUG

Reputation: 239

Shortest path with two objectives

I am interested in writing an algorithm to find the shortest path with two objective (ex. time and safety). For example, in the graph below, black number is the travel time and red number is the probability of a user experiencing an incident. The goal is to find the best path with the best overall cost.

Total cost = time + (probability of an incident in this route)*(time cost of an incident)

What type of problem is this? Is this a NP-hard problem? example

Upvotes: 0

Views: 810

Answers (1)

Alex Reinking
Alex Reinking

Reputation: 20026

First, if your edge weights can be combined via compatible units through convolution, scaling, or something else that results in forming a new ordered semiring, then Dijkstra's algorithm will work as expected over that semiring.

Second, if your edge weights are fundamentally different, you can settle for a Pareto-optimal path. That is, a path for which you cannot improve one criteria without worsening the other. Often, this is the best you can do. Two papers that might be of interest are:

A bicriterion shortest path algorithm by Climacao and Martins

A bicriterion Pareto-optimal path algorithm by Tung and Chew

In your case, if you make some strong assumptions about the events of your "incidents" -- namely that they are mutually exclusive -- then you can replace your edge weights with time + expected time due to an incident.

This is because if X_e is the event that an incident occurs on edge e, then P(X_e1 or X_e2) = P(X_e1) + P(X_e2) - P(X_e1 and X_e2) = P(X_e1) + P(X_e2) by their mutual exclusivity. Then the expected cost of any path e1 ... eN is cost(e1) + ... + cost(eN) + incident cost * P(X_e1 or ... or. X_eN) = cost(e1) + ... + cost(eN) + incident cost * (P(X_e1) + ... + P(X_eN)) = (cost(e1) + incident cost * P(X_e1)) + ... + (cost(eN) + incident cost * P(X_eN)) = E(cost of e1) + ... + E(cost of eN) which is just the sum of the expected costs of each edge, independently of one another.

Upvotes: 2

Related Questions