Quote:
Is there an efficient algorithm for this problem?
None, even worse there can be no solution because of infinite looping.
Quote:
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.
The combination of those criteria can lead to infinite loops.
If you have a loop with negative cost, just 1 more loop will improve any best path infinitely.
Negatives costs prevent any optimization.
You have to rethink your criteria or give details.