Critical edges/ vertices in directed graph

Revision en2, by frying_pan, 2023-07-21 15:45:32

Given a weighted directed graph $$$G$$$ and $$$2$$$ different vertices $$$s$$$ and $$$t$$$ in it. How can we find all edges $$$e$$$ such that removing $$$e$$$ increases the distance between $$$s$$$ and $$$t$$$? Is there a better way then $$$O(E*(E + V))$$$ where we test each edge by removing it? Can we also find all vertices $$$v$$$ defined analogously?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English frying_pan 2023-07-21 15:46:56 21 Tiny change: 'then $O(E*(E + V))$ where' -> 'then $O(E*E*log(V))$ where'
en2 English frying_pan 2023-07-21 15:45:32 9 Tiny change: 'Given a directed ' -> 'Given a weighted directed '
en1 English frying_pan 2023-07-21 15:44:20 349 Initial revision (published)