Сначала , если ваши веса ребер могут быть объединены через совместимые единицы посредством свертки, масштабирования или чего-то еще, что приводит к формированию нового упорядоченного полукольца , тогда алгоритм Дейкстры будет работать какожидается по этому полукольцу.
Секунда , если вес ребер принципиально отличается, вы можете согласиться на оптимальный по Парето путь .То есть путь, по которому нельзя улучшить один критерий, не ухудшая другой.Часто это лучшее, что вы можете сделать.Два документа, которые могут представлять интерес:
Алгоритм кратчайшего пути бикритерия Климакао и Мартинса
Алгоритм оптимального пути бикритерия Парето Tung and Chew
В вашем случае , если вы сделаете некоторые серьезные предположения о событиях ваших "инцидентов", а именно, что они являются взаимоисключающими, тогда вы можете заменить свои граничные весас time + expected time due to an incident.
Это потому, что если X_e является событием, когда инцидент происходит на границе e, то P(X_e1 or X_e2) = P(X_e1) + P(X_e2) - P(X_e1 and X_e2) = P(X_e1) + P(X_e2) по их взаимной исключительности.Тогда ожидаемая стоимость любого пути e1 ... eN равна 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), которая является просто суммой ожидаемых затрат каждого ребра, независимо друг от друга.