진짜 존잘씹멋개존경형들 질문하나있어여

[컴공과(211.223)]

형들 경로찾는 알고리즘 중에서 음수의 간선을 허용하는 알고리즘은 뭐가있어??

플로이드, 다익스트라, tsp, 프림, 크루스칼 이것중에!!

플로이드랑 프림만 마이너스값 가질 수 있을거같은데

맞을까??

[ㅌㅌ(118.38)]

벨만포드

[익명(118.38)]

프림, 크루스칼은 mst 알고리즘이라 경로 알고리즘이랑은 상관없음

[글쓴이(211.223)]

ㅇㅇ // 형 그럼 다익스트라 -> 음의가중치X

[글쓴이(211.223)]

크루스칼, 프림은 음의가중치 허용?

[dd(118.38)]

님이 언급한건 다 안됨.

[익명(223.62)]

플로이드 워샬

[컴공과(211.223)]

형들 교재에서 프림에서 노드간 연결될때 정점에서 확장하는걸로 알고 있는데 음의 수도 되지않을까? 크루스칼은 정점들의 가장 작은수를 힙으로 정렬해서 하나씩 이어가는 부분인데 가능하지않을까?

[익명(118.38)]

음수있어도 되는데 프림이랑 크루스칼은 mst 라니깐 경로랑 상관없음

[컴공과(211.223)]

아 형 고마워여