Shortest path in a directed, unweighted graph with a selection criterion between multiple shortest paths?

2
votes

I am looking for the best way to solve this variation on the shortest-path problem:

I have a directed graph with unweighted edges. I need to be able to find the shortest path between any two nodes, if such a path exists. What makes this problem different than a regular shortest path problem is this: If multiple paths exist with shortest length, I need to be able to choose the path with the highest "authority".

Each node has a numerical authority and the path with the highest authority is simply the one with the highest sum of node authorities.

In summary: I need the shortest path between a pair of nodes in a directed graph, but if there are multiple paths with the same, minimum length, I need to find the one with the highest path authority.

What is the best way to go about doing this? Is there some way to convert this into a weighted graph and then just use Dijkstra's algorithm? Is there some way to modify breadth-first search to give me the set of shortest paths, which I can then iterate through to find the highest authority path?

2
algorithmlanguage-agnosticgraph-theoryshortest-pathbreadth-first-search
It is not. Should I make that more clear in the question? – Grady S

2 Answers

5
votes

The edges are unweighted, so give eacn edge a weight of 1+auth(v,u). [auth is explained in the following line]

for each (v,u) set auth(v,u) = max{authority} - authority(v) (*) [this is true becuase if you use the edge leaving from v, you definetly visited it].

(*)max{authority} is the the highest authority in the graph.

normalize your "auth rank" so, Sigma(auth(v,u),for each (v,u) in E) < 1 [by dividing, so the authority of edges will still be proportional to the original]

now, run dijkstra on the graph with the new modified weights.

The shortest path found must be shortest, because the authority factor cannot overcome the distance factor, because it is to 'weak' [normalized to less then 1].
And it is the one with the highest authority [for vertices], since it is the one with the lowest auth [for edges], since it is minimal.

1
votes

Nothing about Djikstra's algorithm forces you to use a scalar to represent the path cost.

A simple modification would be to use a pair instead of a single value, e.g. (distance, authority) to represent the cost of a path. The ordering would be < distance, then > authority, i.e., lower distance takes higher priority, then higher authority takes priority.