Properties of Shortest Paths
- Strongly connected = every vertex reachable from every other vertex
- Shortest paths normally simple
- Zero-weight edges that form cycles ignored → shortest paths found have no cycles
- Shortest paths not necessarily unique
- May be multiple paths of lowest weight from one vertex to another, content to find any one of them
- Parallel edges & self-loops may be present
- Only lowest-weight among set of parallel edges plays role, no shortest path contains self-loop (except possibly one of zero weight → ignored)
Shortest Paths Tree