DFS를 조금 변형시켜서도 풀이가 가능하다고 알고있지만 저는 각 노드를 방문할 때 최단거리라고 보장할 수 있도록 다익스트라를 사용했습니다.

예시로 1 -> 2 ->3 의경로 15Distance, 1 -> 4 ->3의 경로 5Distance이런식으로요. 

조금 오래된 글이라 보실지는 모르겠지만 저도 비슷한 문제를 겪어 적어봅니다.

1. 구현하신 DFS는 두 노드간에 2개 이상의 간선이 들어왔을 때 최소가 되는 간선만을 저장하지 않습니다. 따라서 노드간 간선 중 먼저 탐색된 간선의 길이가 다른 간선에 비해 길더라도 이미 방문 표시를 하였으므로 최소 거리로 이동할 기회가 사라집니다.

2. 길이가 최소가 되는 간선만 구하더라도 탐색 순서에 따라 최소 거리를 만족하지 못할 수 있습니다. 만약

A -> B -> C ->D
A -> C -> D

와 같은 그래프에서 [ A -> B -> C ] 보다 [ A -> C ]의 거리가 짧은데 전자의 탐색이 먼저 이뤄진다면 이미 C에 방문표시가 되어 최소 거리인 [ A -> C ] 탐색을 무시하게 됩니다. 이런저런 문제 때문에 DFS로 구현시 방문 여부만 기록하는 대신 이동 거리를 기록하고, 다시 이동할 수 있는 경우가 있는 경우 기록한 이동 거리보다 새로운 이동 거리가 짧은지 확인하고 이동하도록 구현하는게 좋아보이네요.