다익스트라 알고리즘을 이용한 지하철 최소환승 구현...

XEN(118.37) 2011.08.10 18:12:42

조회 9340 추천 0 댓글 0

질문이 있습니다.

다익스트라 알고리즘을 이용한 지하철 경로 찾기를 만들고 있는데요.(아래는 메인 소스)

해당 아래 소스를 실행하면 단순히 최소 시간 경로로 나오게 되는데요(이것도 환승할때 추가시간 처리는 안되어 있음)

궁금한것은 아래 굵은 표시가 된 부분에서 환승을 했을 경우 시간값을 약간씩 더해서 최소환승을 구현해야 되는데,

어떤식으로 구현해야 할지 고수님들은 조언부탁드립니다.

참고로 아래 소스는 java로 만들어졌습니다.

private void OnCald() {

int n = 463; // 지하철 역수

int i,j,k=0;

int s=0,e=0,min; // s는 시작노드, e는 도착노드, min은 최소거리를 나타냄

int [] v = new int[n]; // v는 최종적인 확정된 길을 나타냄

int [] distance = new int[n]; // distance는 시작노드에 최종노드까지 최단거리

int [] via = new int[n];

String strStart = myStart.getText();

s = Integer.parseInt(strStart);

String strend = myEnd.getText();

e = Integer.parseInt(strend);

for( j=0; j<n; j++ ) {

v[j] = 0;

distance[j] = m;

}

distance[s] = 0;

for( i=0; i<n; i++ ) {

min = m;

for( j=0; j<n; j++ ) {

if( v[j] == 0 && distance[j] < min ) {

k = j;

min = (int)distance[j];

}

v[k] = 1;

if(min==m) break;

for(j=0; j<n; j++) {

if(distance[k]==m || data[k][j]==m)

continue;

if(distance[j] > distance[k] + data[k][j]) {

distance[j] = distance[k] + data[k][j];

via[j]=k;

}

int nDistance = distance[e];

String strResult = "최단거리:" + Integer.toString(nDistance) + " 입니다." + "\\n";

int path[] = new int[n];

int path_cnt=0;

k=e;

while(true) {

path[path_cnt++]=k;

if(k==s)break;

k= via[k];

}

strResult = strResult + "경로:";

for(i=path_cnt-1;i>=1;i--) {

Stn_Seoul row = (Stn_Seoul) m_vector.elementAt(path[i]);

strResult = strResult + row.GetName() + "(" + Integer.toString(path[i]) + ")" + " -> ";

}

Stn_Seoul row = (Stn_Seoul) m_vector.elementAt(path[i]);

strResult = strResult + row.GetName() + "(" + Integer.toString(path[i]) + ")" + "입니다.";

m_Result.setText(strResult);

}

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	연예인하면 더 인기 많을 것 같은 스포츠 스타는?	운영자	24/09/16	-	-
264675	내가 느끼기엔 대한민국과 개발자는 어울리지가 않아. [9]	천재해커(121.139)	11.08.18	219	0
264674	님들 c다음 뭐배웟츰? [4]	오마이갓넬	11.08.18	104	0
264673	어떤 회사로 가야될지... [5]	드리프트(61.101)	11.08.18	101	0
264672	갑자가 환상적인 어플 아이디어가 떠올랐다!!! [3]	거칠게	11.08.18	208	0
264671	아래 프로그램 올려봅니다(조공 有) [14]	늅뉴뉴	11.08.18	255	0
264670	또 다시 말하지만 프갤은 차캐슴미다 [1]	데덴찌	11.08.18	46	0
264669	Tree형 구조에서 질문여! [4]	씨플+(123.109)	11.08.18	45	0
264668	니들 SI랑 SM의 차이가 뭔지 알아? [1]	데덴찌	11.08.18	157	0
264667	삼성은 프로그래머가 2000명이나 되니까 다만들수있을거같으데... [5]	ㅇ(61.77)	11.08.18	181	0
264666	프갤은 차캤다 [1]	데덴찌	11.08.18	41	0
264665	자바스크립트에서 왜 month만 +1을 해줘야하는거냐.ㅡ.ㅡ; [7]	blackd	11.08.18	85	0
264664	역시 카페가쩔지 [1]	Agangs	11.08.18	51	0
264663	너네 퇴근 안하니 끵끵 [1]	데덴찌	11.08.18	33	0
264660	프로그래머 횽들아 이 프로그램 100프로 해킹프로그램이지?? 함 봐죠요 [5]	늅뉴뉴	11.08.18	161	0
264658	매크로 익스프레스 막혔네;; [1]	늅뉴뉴	11.08.18	120	0
264657	애미없는 정전엔 은꼴 [1]	SuCo	11.08.18	116	0
264656	소스 분석좀 부탁드림 [11]	데덴찌	11.08.18	114	0
264655	삼성이 안드로이드 걷어찬 이야기를 누가 칼럼으로 썼네... [11]	분당살람	11.08.18	220	0
264653	그런데 정말 궁금해서 그러는데 개발자분들 꼭봐줘 [7]	좋은아버지	11.08.18	108	0
264652	오늘부터 쉬고, 공부는 다음주부터.... [1]	ㅋㄱ(183.96)	11.08.18	42	0
264651	나 라면 잘안먹는데 꼬꼬면 맛있음.. [5]	SuCo	11.08.18	130	0
264650	야호 승리의 함수 [3]	mercedes㉦benz	11.08.18	53	0
264647	우리의 갑인 구글님을 숭배하자~ [8]	분당살람	11.08.18	103	0
264645	횽들 질문 하나만 싸지를게	디폴팅(210.118)	11.08.18	44	0
264644	칼퇴 [1]	CLASSIC	11.08.18	40	0
264643	Suco는 봅니다 [28]	+어게인	11.08.18	120	0
264642	프겔에서 여자는 이제 그만 찾쟈.... [2]	blackd	11.08.18	98	0
264640	여자이고 싶다. [5]	mercedes㉦benz	11.08.18	74	0
264639	새;끼들아 프갤에 여자가 없을꺼냐? [3]	데덴찌	11.08.18	87	0
264638	열강 C++	전원버튼	11.08.18	59	0
264637	서브웨이 쩌네.. 우리도 이런 발상의 전환이 필요함 [1]	허허벌판	11.08.18	91	0
264636	ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ C++ [5]	McHello	11.08.18	112	0
264635	열혈강의.....조낸 지루하네;;; [4]	전원버튼	11.08.18	159	0
264632	형님들 이 과목 뭐하는건지 좀 봐주세요 [7]	전방수류탄＊	11.08.18	105	0
264631	회사다니면 꼭 하고 싶은게 있었는데... [4]	좋은아버지	11.08.18	92	0
264630	밥 먹으면 배 나오는거 왜 그러냐??? [1]	ㅁㄹ(180.227)	11.08.18	421	2
264629	투명한 문자좀 알려주세요	■ゆい	11.08.18	59	0
264628	왜케 소방방재청에서 문자가 오는거야..	blackd	11.08.18	35	0
264627	님들 저 열혈강의 저자한테 강의받음.. [9]	SuCo	11.08.18	159	0
264626	함수명들 어떰?? [4]	mercedes㉦benz	11.08.18	71	0
264624	여자 사람은 결국 자기 하기 나름이라고 생각해 [3]	좋은아버지	11.08.18	103	0
264623	이쪽계열 형님들(누님은 업을테니)성향에 대해서 궁금한게 있는데요 [8]	파워컴공(218.237)	11.08.18	83	0
264622	우리는 3포 세대인데 무슨 여자냐~	거칠게	11.08.18	59	0
264620	문민 -> 국민 -> 참여 -> ??? [2]	iljeomobolt	11.08.18	56	0
264618	근데 공대생 진짜 여자한테 인기 없어요? [12]	파워컴공(218.237)	11.08.18	236	0
264617	인터넷서 추적 당하지 않는 방법... [2]	iljeomobolt	11.08.18	103	0
264616	프로그래밍 언어라는것도 언어적 능력이 필요한 겁니까? [8]	파워컴공(218.237)	11.08.18	123	0
264615	연애는 왕슴가, 결혼은 보통으로... [3]	우왕국킹짱왕	11.08.18	191	0
264612	여기 능력자님들 포샵도 잘하시나요 뺑소니 번호판점 ㅜㅜ [4]	뺑소니를잡자(210.178)	11.08.18	98	0
264610	학교에서 자바 가르치는건 진도 뺀다고 이것저것 스킵해서.. [3]	ㅇㅇㅁㅇㄻㅁ	11.08.18	97	0