프로그래밍

3204,

1/161

218darkest

http://-

[알고리즘] 최단경로 알고리즘으로 짜는건데요 도와주세요 ㅠ

http://www.hackerschool.org/HS_Boards/zboard.php?id=QNA_programming&no=2754 [복사]

안녕하세요 학생인데요
과제가 있는데 도와주세요ㅠ
알고리즘을 적용하여 간단한 프로그램을 짜는건데요
문제는 이렇습니다.
최단거리 구하는건데요
다수의 정점이 있고 그 정점간의 거리가 각각 달라요
최단경로의 길이를 구하는 알고리즘을 이용하여
최단경로를 구해야해요
예를들어 정점123456789 중에 1에서 4로 가는 최단경로로 선택된 정점이 1-5-3-6-2-4라면
일단 1~4로 갔다가 다시 4~1로 돌아오는데
다시 돌아갈 때는 처음에 거쳐갔던 정점 5-3-6-2를 제외한 나머지 정점 중에서 최단경로의 길이로 4~1로 다시 돌아와야해요
지금 닥친 문제는 이거에요

1. 방향그래프로 해야할것인가 무방향그래프로 해야할것인가..
2. 어떤 알고리즘을 적용해야할까요?
플로이드 알고리즘을 생각하고 있었는데 출발점과 도착점지정하기가...
플로이드 알고리즘은 출발점이 따로 없고 모든 정점을 거치는 최단경로에요..
3. 알고리즘을 정했다면 갔을때 정점을 어떻게 제외시켜야 될까요??
4. 가장 중요한 문제... 처음 갔던 최단경로를 제외하고 돌아오려면 출발점과 도착점이 중간정점과 적어도 2개이상의 연결선을 가지고 있어야 중복이 안되는데.. 연결선이 하나밖에 없는 정점을 만나면 어떻게 할까요?그냥 2개이상 존재한다는 가정하에 시작해야하나요?

아직 초보여서 많이 했갈리고 어렵네요 뼈대좀 잡아주세요
부탁드려요 ㅠ

Hit : 7886 Date : 2010/11/05 01:03


kanate	kaist ? ㅋㅋ	2010/11/06
crownw	죄송한데.. 과제는스스로....ㅎㅎ	2010/11/06
dawon15	이틀전에 질문 보고 저도 이틀동안 꼬박(응?) 생각해봤는데... 다익스트라 라는 알고리즘을 발견했습니다 그건 어떨가요..? 플로이드가 모든 점을 지나가는 것 이라면 다익스트라는 한 점에서 다른 모든 점으로 가는 최단경로를 구하는 것 이라네요... 그러니 한번 시도 해 볼만은 할거에요 ... .. (ps 절대 맞는 답변은 아닙니다 ㅠ_ㅇ)	2010/11/08