[일반] Dinic이랑 Push-Relabel 차이 아는분?

[대학원오지마세..(publfl)]

Push-Relabel Algorithm 보고 있는데 Dinic Algorithm이랑 다른게 뭔지 모르겠네

len(u) = len(v)+1인 순서대로 찾아가고,

relabel할때 capacity가 있으면 사이에 edge 있다고 가정하고 mindist 갱신해주는데

이게 Dinic에서 했던 level graph/block 개념과 뭐가 다른거지?

알고리즘 이해가 잘 안된다

[익명(172.224)]

https://gist.github.com/Chillee/ad2110fc17af453fb6fc3357a78cfd28

[대학원오지마세요(publfl)]

오 그러니까 Push-Relabel이 Dinic보다 훠어어얼씬 빠른데 대신 edge의 flow량이 몇인지는 모르는거구나 ㄳㄳ PS에서는 간선복구할 일이 더 많으니까 Push-Relabel 짤생각 말고 그냥 Dinic으로 계속 해야겠구먼;

[익명(104.28)]

https://ocw.mit.edu/courses/sloan-school-of-management/15-082j-network-optimization-fall-2010/lecture-notes/MIT15_082JF10_lec12.pdf
이거좋다 excess scaling 개념부터가 dinic과는 다르구만

[대학원오지마세요(publfl)]

ㄳㄳ 읽어봄

[익명(121.172)]

https://koosaga.com/287

[대학원오지마세요(publfl)]

아니 한달전에 적은거네; 내 주위 사람들도 요즘 Push-Relabel 얘기하길래 찾아본건데, 혹시 요즘 고인물들 사이에서 유행하는건가?