학술논문
SPFA를 기반으로 개선된 벨만-포드 알고리듬
이용수 11
- 영문명
- An improved Bellman-Ford algorithm based on SPFA
- 발행기관
- 한국전자통신학회
- 저자명
- 진호(Hao Chen) 서희종(Hee-Jong Suh)
- 간행물 정보
- 『한국전자통신학회 논문지』제7권 제4호, 721~726쪽, 전체 6쪽
- 주제분류
- 공학 > 전자/정보통신공학
- 파일형태
- 발행일자
- 2012.08.30
4,000원
구매일시로부터 72시간 이내에 다운로드 가능합니다.
이 학술논문 정보는 (주)교보문고와 각 발행기관 사이에 저작물 이용 계약이 체결된 것으로, 교보문고를 통해 제공되고 있습니다.
국문 초록
이 논문에서 SPFA(shortest path faster algorithm)을 사용해서 기존의 벨만-포드(Bellman-Ford)을 개선한 효율적인 알고리듬을 제안한다. 벨만-포드 알고리듬은 딕스트라(Dijkstra) 알고리듬과 다르게 부(-)인 가중치를 갖는 그래프에서 사용할 수 있다. SPFA 알고리듬은 한 대기열을 이용하여 노드를 저장한다. 그래서 중북을 피할 수 있다. 벨만-포드 알고리듬은 시간을 더 사용하여 노드 표를 업데이트를 시킨다. 이 개산 알고리듬에서는 인접 리스트를 이용하여 표의 각 노드를 저장한다. 한 대기열을 통하여 데이트를 저장한다. 개선 방법에서는 새로운 점에 계속 relaxation을 통하여 최적 패스를 얻을 수 있다. 딕스트라 알고리듬과 SPFA 알고리듬과 개선된 알고리듬의 성능을 비교하기 위해서 시뮬레이션을 하였다. 실험 결과에서 랜덤(random) 그래프에서 개선된 알고리듬, SPFA 알고리듬과 딕스트라 알고리듬은 효율이 비슷했었는데, 격자형 지도에서 개선 알고리듬
의 효율이 더 높았었다. 처리시간에서 개선된 알고리듬은 SPFA 알고리듬 보다 3분의 2를 감소시켰다.
영문 초록
In this paper, we proposed an efficient algorithm based on SPFA(shortest path faster algorithm), which is an improved the Bellman-Ford algorithm. The Bellman-Ford algorithm can be used on graphs with negative edge weights unlike Dijkstra's algorithm.
And SPFA algorithm used a queue to store the nodes, to avoid redundancy, though the Bellman-Ford algorithm takes a long time to update the nodes table. In this improved algorithm, an adjacency list is also used to store each vertex of the graph, applying dynamic optimal approach. And a queue is used to store the data. The improved algorithm can find the optimal path by continuous relaxation operation to the new node. Simulations to compare the efficiencies for Dijkstra's algorithm, SPFA algorithm and improved Bellman-Ford were taken. The result shows that Dijkstra's algorithm, SPFA algorithm have almost same efficiency on the random graphs, the improved algorithm, although the improved algorithm is not desirable, on grid maps the proposed algorithm is very efficient. The proposed algorithm has reduced two-third times processing time than SPFA algorithm.
목차
Ⅰ. Introduction
Ⅱ. Related Algorithm
Ⅲ. Improving the Search Method
Ⅳ. Results of Experiment
Ⅴ. Conclusions
References
해당간행물 수록 논문
- 형태소 분석기의 어휘적 중의성 해결에 관한 연구
- 웹 사용자 누적 사용정보 기반의 키워드 검색 모델
- 측면산화 프리크리닝의 최소화를 통한 DRAM의 데이터 유지시간 개선
- DCT, DWT와 신경망을 이용한 심전도 부정맥 분류
- LED를 이용한 기타운지법에 대한 연구
- ns-2 시뮬레이터를 이용한 TCP 재전송 손실 복구 알고리듬의 구현
- 고령세대의 환경과 헬스 케어 시스템 주택에 관한 연구
- 1V 미만 전원전압 동작에 적합한 혼성 평형 전압제어 발진기
- 성인의 흡연과 치주질환의 관련성
- NFC 보안 채널을 위한 인증 알고리즘에 관한 연구
- SPFA를 기반으로 개선된 벨만-포드 알고리듬
- 한국의 글로벌 과학기술협력 연구
- 클라우드 환경에서 확장성을 지원하는 트랜잭션 처리 방법
- 선형시변 발진기 위상잡음 이론의 전력 보존성의 증명
- 전자상거래 발전 로드맵 모델
- 우리나라 청소년의 흡연 경험과 인터넷 중독과의 관련성
- AC 서보모터에 대한 견실한 외란억제 제어
- 등산법을 이용한 한국어 맞춤법 교정기의 분석
- 클라우드 컴퓨팅 기반 스트리밍 미디어의 검색 가능 이미지 암호 시스템의 설계
- 유한체상의 방정식과 m-수열의 상호상관관계 분석
- FMCW 레이더 주파수합성기용 델타-시그마 변조기의 시뮬레이션
- 이동단말의 로밍에 따른 VoIP 서비스 품질 분석
- 자성물질을 가속시키기 위한 전류 Segment 코일의 설계
- 비데용 유비쿼터스 헬스케어 모듈 개발
- Gaussian 혼합모델 기반 조명 변화에 강건한 연기검출 알고리즘
- 폴리머 테이퍼링 도파로 영역이 있는 저 손실 플라스틱 광섬유 커플러
- HDLC(High-level Data Link Control) 프로토콜에서 효율적 문자부호 전송을 위한 문자부호화 규칙
- 해양 USN 환경에서 수질환경의 온라인 정상․비정상 상태 구분
- 데이터통신 전송효율과 라틴어 부호 체계 고찰
- MANET 기반 MD5 보안 라우팅에 관한 연구
- SWOT분석을 통한 한국 마이크로 로봇의 발전방안
- 상호상관관계 함숫값이 4개인 새로운 데시메이션
참고문헌
교보eBook 첫 방문을 환영 합니다!
신규가입 혜택 지급이 완료 되었습니다.
바로 사용 가능한 교보e캐시 1,000원 (유효기간 7일)
지금 바로 교보eBook의 다양한 콘텐츠를 이용해 보세요!