[질문] 다익스트라로 최장거리 구할 수 있음?

[익명(1.238)]

유방향 그래프 노싸이클에서 다익스트라로 최장거리 구할 수 있나요?

아무생각없이 최단거리 구하는거랑반대로 하면되겄지 했는데

생각해보니까 안 될 것 같기도..?

[익명(14.52)]

됨

[익명(106.102)]

그 조건이면 걍 간선 가중치 음수로 꺾고 나온 결과에 음수취하면 될듯 - dc App

[익명(1.238)]

ㄷ.ㄷ 천재임?

[익명(210.105)]

다익은 간선 가중치 음수면 안되는데

[익명(1.240)]

최솟값의 절댓값만큼 더해주면 되는거지 - dc App

[익명(1.240)]

그리고 간선 몇개 지나왔는지 카운트해서 후처리 - dc App

[익명(220.76)]

후처리는 어떻게 해요 이거 글 보는데 이해가 잘 안됨

[익명(210.105)]

그냥 안되는게 간선 개수도 답에 영향을 주는데 어떻게 후처리를 함

[익명(210.105)]

그리고 다익스트라 철학 자체가 현재 최단경로 값이 확정 안 된 애들 중에 가장 작은 애는 음수 간선이 없어서 그거보다 작아질 수 없기 때문에 그게 답임을 확정시킬 수 있다는 것에 있는데...

[EN_SA(encludingsalt)]

DAG면 그냥 DP쓰고말지

[익명(218.55)]

싸이클이 없으면 가능 - dc App

[익명(118.235)]

될거같긴한데 어캐해야할진 모르겠다

[익명(210.105)]

그냥 이건 위상정렬 대표 문제고 다익은 여기 낄 애가 아닌 듯. DAG 아니라고 하면 음수가중치 주고 벨만포드 돌리면 됨. 내 생각에 더 빨리 푸는 건 불가능한게 만약 가능했으면 음수 가중치 있는 최단경로 문제도 O(ElogE)에는 풀려야 되서 아무도 벨만 포드 안 썼을 듯.

[익명(175.203)]

최소 힙의 반대로 값의 반대부호도 저장해서 최대힙 구현하듯이 만들면 될거 같아보이네

[익명(211.36)]

최장거리가 그리디한 방법으로 됨??

[익명(121.150)]

얘들아 최장거리 NP다. 저건 사이클 없는 DAG여서 되는거다. 만약 무향이면 포레스트고.

[익명(210.105)]

그건 simple path일 때고 그 조건 없으면 벨만포드로 풀리는게 맞음