잘 알고 계십니다. 다익스트라 알고리즘은 모든 점을 지나는 것이 아닌, 그냥 목적지까지 가장 빠르게 도달하는 알고리즘이죠.

모든 점을 다 거쳐야만 한다면, 이건 순회 세일즈맨 문제(Travelling salesman problem, TSP. ,스펠링 맞는지 몰것음.) 입니다. 단, 원래 점으로 되돌아 올 필요는 없으니, 약간 변형된 순회 세일즈맨 문제입니다.

이건 수학적으로 NP 하드에 해당하며, 경우의 수를 다 때려박는 것 외에는 최적을 한방에 찾아내는 알고리즘 따위는 없습니다.

저라면 이렇게 풀겠습니다.

1. 적당히 대충 솔류션을 하나 찾는다.
2. 1의 코스트를 기록
3. 유전알고리즘으로 1~2 과정을 몇 번 반복.
4. 이제 꽤 괜찮은 코스트를 가진 경로를 하나 찾았을 거임. 여기까지는 굉장히 신속하게 풀림. 이 수 차례에 걸쳐 찾아낸 미니멈 코스트를 V라고 한다.(아직 V는 최적해라고 증명되지 않았다)
5. 이제 모든 경우의 수를 다 탐색하되, 단 아래와 같은 조건을 어길 경우, 이미 싹수가 노란 솔류션이므로 탐색을 중단하고 바로 다음 단계로 넘어간다.

- [지금 방문하고 있는 노드까지의 코스트] + [전체 패스 코스트 중 미니멈패스코스트]*[남은노드수] >= V 일 경우, 싹수가 노랗다.

- 지금 방문한 노드가, 들어오기만 하고 나갈 방법이 없는 노드일 경우

1. 5의 조건을 다 뚫고, 모든 노드를 다 방문했는데 , 그 코스트가 V보다 작다면, V를 업데이트하고 지금부터 개선된 V로 나머지 경우의 수를 다 방문한다.

2. 더 이상 조합이 없으면 종료한다. 지금까지 찾아낸 V와 그 경로가 최적경로.

H = { [전체 패스 코스트 중 미니멈패스 코스트]* [남은 노드 수] } 는 가장 옵티미스틱하게 남은 경로의 길이를 예측하는 부분인데, 이 부분을 개선하면 좀 더 성능이 나을 겁니다. 예를 들어서 전체 패스 길이에 대한 리스트를 가지고 있으면서 그걸 소팅해서 작은 순서로 정렬한 리스트를 가지고 , 순서대로 어큐뮬레이트 해 놓은 리스트를 만든 다음에, H 대신에 남은 노드 수에 해당하는 리스트의 요소를 가지고 와서 더해준다던가 해도 되겠죠.

요는, 얼마나 싹수가 노란 놈을 빨리 판단해서 끝까지 다 탐색하지 않고 중간에 잘라내는가 입니다.

그 외에는, 멀티코어를 활용해서 짤 수 있다면, 역시 극적으로 시간이 줄어들 겁니다.