nayabin   2달 전

안녕하세요?

노드와 엣지가 약 10~20만개일 때,

최대 2개의 엣지의 가중치를 1로 바꿔서 얻을 수 있는 최단경로는 어떻게 구할 수 있을까요?

여러 방향으로 생각해 봤는데 이거다! 하는 답이 나오질 않네요..

어떻게 하면 될까요? 도움 부탁 드립니다!!



sksdong1   2달 전

D[n][k]  (0<=k<=2)

시작점에서 n번 도시까지의 최단 경로는 min(D[n][k]) (0<=k<=2) 

n의 도시에 k개의 엣지를 바꿔서 온 최단 경로라고 구하면 될 거 같네요


nayabin   2달 전

sksdong1 댓글 감사합니다.

엣지의 갯수 말고 어떤 엣지를 바꿧는지에 대한 정보는 어떻게 고려되는건가요?

kks227   2달 전

어떤 엣지를 바꿨는지의 정보는 필요없을 것 같은데,

만약 어떤 엣지를 바꿨는지를 기억하지 못하고 바꿨던 엣지를 또 바꾼다면 원래는 소비되지 않아야 할 비용이 그만큼 낭비되겠지만

그건 다른 데다 써도 될 바꾸기연산을 쓸데없이 허비한 거라 득이 안 되고, 따라서 다른 경로를 바꾼 더 좋은 경로가 반드시 있어서 그 답에 묻혀버릴것 같네요.

예를 들면 정점 u, v가 있을 때 u->v->u로 돌아오면서 경로를 2번 바꾸고 다음 정점 w로 이동하는 경로보다는

당연히 그냥 u에서 바로 w로 이동하는 게 더 짧은 경로를 만들 것이고... 따라서 경로 u->v->u는 묻혀버릴 겁니다.

noeffserv   2달 전

경로를 역추적하면 가장큰 에지 두개 혹은 한개를 알아낼수 있습니다.

nayabin   2달 전

아래와 같이 생각을 해봤는데요..

인접한 노드들에 대해서 min 값을 구한다면 계산 순서에 영향을 받을 것 같아서 안될 것 같습니다.

D[n][1] = min(D[n][0] + 1, D[n][1] + W, ... 모든 인접한 노드들에 대해서)


점화식으로 알려주실 수 있을까요? ㅠ.ㅠ

sksdong1   2달 전

계산 순서를 다익스트라로 가중치 적은것부터 계산해 나가면 되지 않을까요

댓글을 작성하려면 로그인해야 합니다.