Search code examples
mathtreecomputer-sciencegraph-theory

What is an slack of an edge in Graph Theory? And why does the slack of an edge need to be zero for shortest path trees?


I understand the formula for a slack but can anyone explain in normal terms and what it signifies in the big picture? Also, why does the slack of an edge need to be zero for shortest path trees?


Solution

  • In most cases, slack is just "unused capacity". If you have a maximal flow on an edge, and the actual flow over an edge for some configuration, the slack is the difference.