'determine if the shortest path in a graph is unique
Say I have a cyclic graph containing bi-directional and parallel edges e.g.
Assume all edge weights equal 1.
- How would I determine if the shortest path is a unique path?
- How would I determine if the shortest path that satisfies an edge or node invariant is a unique path? (e.g. Artemis to Egglesberg, only blue edges)
- How would I determine if the shortest path that satisfies a path invariant is a unique path? (e.g. Artemis to Egglesberg, must go through Dentana)
Potential solution:
- Set all the edge weights in the shortest path equal to the total number of edges in the graph
- If the new shortest path is identical to the old path, then the path is unique.
However, I haven't tested this solution and it may not be optimal.
EDIT: this approach seems to work with the caveat that it will throw away cycles back to the starting node e.g. class-> material is considered unique b/c class->professor->address->student->class_student->class->material introduces a cycle back to the starting node. this cyclic path is treated as invalid.
Non-goals: finding all paths, finding the longest path.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|


