사진과 같이 S에서 D로 가야하는 다이그래프가 존재하는데, 여기서 B,D 간선이 음수의 가중치를 가지고 있고, 문제에서는 다익스트라 알고리즘을 이용해서 각 단계에 맞춰서 어떻게 알고리즘이 작동하는지 적으라는데 총 배열 3개를 이용합니다.
distance : 지금까지 발견한 최단 경로의 가중치 합을 저장한다.
found : 최단경로가 결정되었는지 여부를 판별.
pi : 최단 경로 비용을 줄인 노드 id 저장.

이런식으로 되어있는데. 각 배열은 index 5까지 총 6개를 저장가능하고
step 1(init) 부터 시작해서 step 5까지 나와있습니다.

여기서 제가 궁금한건 다익스트라 알고리즘은 간선의 가중치가 음수가 있으면 제대로 작동하지 않는다고 알고있는데, 그럼 이문제에서는 제대로 작동하지 않겠지만 그 과정을 작성하라는 것으로 보이는데 이렇게 풀었을때 (S:0, A:1, B:2, C:3, D:4, E:5)

Step 1 (initialization)

distance

0 1 2 3 4 5

0 1 inf 2 inf inf

found

0 1 2 3 4 5

1 0 0 0 0 0

pi

0 1 2 3 4 5

0 0 -1 0 -1 -1

Step 2 (A로 확장)

distance

0 1 2 3 4 5

0 1 7 2 inf inf

found

0 1 2 3 4 5

1 1 0 0 0 0

pi

0 1 2 3 4 5

0 0 1 0 -1 -1

Step 3 (C로 확장)

distance

0 1 2 3 4 5

0 1 7 2 5 inf

found

0 1 2 3 4 5

1 1 0 1 0 0

pi

0 1 2 3 4 5

0 0 1 0 3 -1

Step 4 (B로 확장)

distance

0 1 2 3 4 5

0 1 7 2 5 9

found

0 1 2 3 4 5

1 1 1 1 0 0

pi

0 1 2 3 4 5

0 0 1 0 3 2

여기서 문제가 좀 헷갈리는데

Step 5 (B에서 D로 확장)

distance

0 1 2 3 4 5

0 1 7 2 4 9

found

0 1 2 3 4 5

1 1 1 1 1 0

pi

0 1 2 3 4 5

0 0 1 0 2 2

Step 4까지는 어찌어찌 진행했는데 Step 5에서 B를 D 혹은 E로 가야하는데 E까지 found를 1로 만들려면 Step 6가 있어야 하지 않나 라는 생각을 했는데 애초에 문제부터 좀 이상하더라고요.

**"음수의 가중치"**를 가진 **"다이 그래프"**에서 **"다익스트라 알고리즘"**을 쓴다는게 이해가 안되더라고요. 그래서 전혀 어떻게 써야할지 감이 안잡혀서 물어봅니다.

궁금한점 요약

음수 가중치를 가진 간선이 있는 다이 그래프에서 다익스트라 알고리즘을 쓸수 있는지
사용은 가능하더라도 어떤식으로 나타내야하는지
일단 지금 적은대로 하는게 맞는지

아무튼 질문조차도 갈피를 못잡겠습니다. 문제가 잘못됐나 싶었는데 아무리 해석해도 틀린점은 없네요.