'Directed SPT vs SPT?

Question:

If a graph contains no negative-weight cycles, does there exist an ordering of edges such that Bellman-Ford computes shortest paths by relaxing each edge at most once?

Answer:

Yes, if there are not negative weight cycles, there exists a directed shortest path tree (SPT). Relaxing in a topological sort order of that tree will only relax each edge once.

My Questions:

  1. Does it mean at first we should find SPT, then find topological order, then use this order for relaxing edge?

  2. Why is word "directed" used to modify SPT?

algorithmdata-structurestreegraph-theory


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions