[일반] 금광세그 짤줄 아는 여자가 이상형인데

[익명(147.47)]

어디가면 만날수 있냐??

ps얘기) 존슨 알고리즘을 이용하면 음수 간선이 적은 개수만 존재하는 그래프에서 최단 경로를 빠르게 구할 수 있다.

[익명(180.70)]

미친놈ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[익명(211.246)]

https://m.dcinside.com/board/ps/4618

[익명(112.152)]

컴공중에서 찾아봐

[익명(121.172)]

음수 간선이 적으면 벨만 포드가 빨리 끝나나..? 아닌 거 같은데

[익명(147.47)]

벨만포드랑 다른거야!
https://en.wikipedia.org/wiki/Johnson%27s_algorithm

[익명(121.172)]

0 짜리 달고 벨만 포드 돌리는 거 아님?

[익명(147.47)]

아 그런가? roads and planes랑 헷갈린듯 전혀 다른 상황이네 미안ㅋㅋㅋ

[익명(118.235)]

존슨은 플로이드와샬보다 빠르네 근데 ps하면서 쓸일은 없을 듯 음수간선 그래프에서 다익스트라 돌리는 테크닉정도만 알면 될듯하네

[익명(211.219)]

음수에서 어떻게 다익스트라 돌려요?

[익명(77.103)]

방향그래프에서 음수 사이클이 없으면 벨만포드 돌려서 포텐셜 함수를 만들어줄 수 있음. 간선의 가중치함수 c에 대한 포텐셜 함수란, c(u,v) + phi(u) - phi(v)가 항상 0 이상이 되는 노드 위에서 정의된 함수 phi를 말함.

[익명(77.103)]

이렇게 포텐셜함수를 O(NM)의 시간에 벨만포드 (또는 SPFA)를 돌려서 구했다면, 새로운 가중치 함수 c'(u,v) = c(u,v) + phi(u) - phi(v)는 항상 0 이상이므로 이 위에서 다익스트라를 돌리면, 예를 들어서 s-t간 최단경로가 s - v_1 - v_2 - ... - v_k - t라면, 경로 가중치 합은 c'(s,v_1) + c'(v_1,v_2) + ... + c'(v_k, t)가 되는데, 계산하면 c(s,v_1) + c(v_1,v_2) + .. .+ c(v_k,t) + phi(s) - phi(t)가 나옴. 따라서, c' 위에서 s-t간 최단경로나 c 위에서 s-t간 최단경로나 가중치 합은 상수 phi(s) - phi(t)만큼 차이나게 됨.

[익명(77.103)]

상수만큼 차이나기 때문에 결국 c 위에서 최단경로 구하는걸 음수값이 없는 c' 위에서 최단경로 구하는걸로 대체할수 있다.

[익명(77.103)]

실제로 이 아이디어를 Mincost Maxflow 알고리즘을 약간 개선할때 사용함. 보통 mincost maxflow를 구할때 spfa나 벨만포드를 매번 사용하는데, 이것이 시간복잡도상 비효율적이라서 포텐셜함수를 미리 구해놓고 다익스트라를 돌리는걸로 대체할 수 있다. 여기서 관건은 매번 최단경로를 찾아서 flow를 갱신해줄 때마다 residual graph가 약간 바뀌게 되므로 포텐셜 함수도 그에 맞춰 조정해야하는데, 선형시간에 항상 조정할수 있음을 체크할 수 있음.

[익명(211.207)]

여태 알고리즘동아리 알고리즘스터디 PS그룹 몇년 하면서 다이아급 문제 푸는 여자 딱 한명 봄

[꼬마개발자(puleugo)]

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[익명(39.7)]

구글

[익명(8.38)]

좋은데