'determine if the shortest path in a graph is unique

Say I have a cyclic graph containing bi-directional and parallel edges e.g.

examplegraph illustration

Assume all edge weights equal 1.

  1. How would I determine if the shortest path is a unique path?
  2. 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)
  3. 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:

  1. Set all the edge weights in the shortest path equal to the total number of edges in the graph
  2. 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.

second graph illustration

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