소개글
본 프로그램 소스는 문제에 제시된 입력데이터에 대해, 사용자가 지정하는 특정 노드로부터의 다른 모든 노드에 대한 최소 비용을 얻어내도록 짜여졌습니다.
-----------문제-------------
8 //노드의 수
0,2,-1,-1,-1,3,-1,-1 //1번 노드의 초기값
2,0,1,4,-1,-1,-1,-1 //2번 노드의 초기값
-1,1,0,-1,3,-1,-1,-1 //3번 노드의 초기값
-1,4,-1,0,3,-1,2,-1 //4번 노드의 초기값
-1,-1,3,3,0,-1,-1,4 //5번 노드의 초기값
3,-1,-1,-1,-1,0,6,-1 //6번 노드의 초기값
-1,-1,-1,2,-1,6,0,4 //7번 노드의 초기값
-1,-1,-1,-1,4,-1,4,0 //8번 노드의 초기값
설명) 0,2,-1,-1,-1,3,-1,-1 //1번 노드의 초기값 경우
1번 노드에서 1번 노드까지의 cost가 0(자기 자신)
1번 노드에서 2번 노드까지의 cost가 2(연결됨)
1번 노드에서 3번 노드까지의 cost가 -1(직접 연결되어 있지 않음)
1번 노드에서 4번 노드까지의 cost가 -1
1번 노드에서 5번 노드까지의 cost가 -1
1번 노드에서 6번 노드까지의 cost가 3(연결됨)
1번 노드에서 7번 노드까지의 cost가 -1
1번 노드에서 8번 노드까지의 cost가 -1
각 노드별 최단거리를 구하는 c언어로 작성된 프로그래밍을 구하라.
-------------------------------------------------------------------
최대한 소스 코드를 짧게 하기 위해, 문제에서 제시된 `최단거리`(최소비용)만을 산출해내며,(경로는 별도로 저장하지 않음) 복잡한 자료구조를 사용하지 않고 입문자~중급자 수준의 완성도가 되도록 배열만 사용하였습니다.
주석은 모든 라인에 상세하게 달려있으니 다익스트라 알고리즘을 이해하는데도 도움이 되시리라 생각합니다.
C언어로 작성되었으며,윈도우 환경에서 빌드하였습니다. 리눅스에서 빌드하실 경우 소스 코드 맨 끝의 system("pause");라는 라인을 없애고 getchar(); 로 변경하여 사용하시면 됩니다.
알고리즘 공부에 많은 도움 되시길 바랍니다.
컴파일 실행환경
Microsoft Visual C++ 6 / Microsoft Visual Studio 2010
참고 자료
없음