기본 콘텐츠로 건너뛰기

개발 공부 - [그래프 알고리즘] 순회 - 최단경로(shortest path problem) - 1

최단경로
- 가중치 (방향) 그래프 G = (V,E), 즉 모든 에지에 가중치가 있음.
- 경로 p = (v0, v1, ... vk)의 길이는 경로상의 모든 에지의 가중치의 합
- 노드 u에서 v까지의 최단경로의 길이를 δ(u, v)라고 표시하자.

 
최단경로문제의 유형
- Single-source 
: 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라.


- Single-destination
: 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라.
* single-source와 singled-destination은 사실상 같은 것으로 볼 수 있다.


- Single-pair
: 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라.
* 최악의 경우 시간 복잡도에서 Single-Source 문제보다 나은 알고리즘이 없을 수 있다.


- All-pairs
: 모든 노드 쌍에 대해서 최단 경로를 찾아라.


최단 경로와 음수 가중치
- 음수 가중치 
: 가중치가 음수인 경우

- 음수 사이클이 있으면 최단 경로가 정의되지 않는다.

* 알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고, 그렇지 않은 경우도 있다.


최단 경로의 기본 특성
- 최단 경로의 어떤 부분경로도 역시 그 부분에 대한 최단 경로이다
* 전체 u~v에서, u에서 v까지의 최단 경로를 지정했을 떄,
중간 위치의 x~y 가 있다면 이 경로는 x에서 y까지의 최단경로이다.

- 최단 경로는 사이클을 포함하지 않는다.
( 음수 사이클이 없다는 가정 )



Single-source (one to all) 최단경로문제
- 입력 : 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 s ∈ V
- 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다.

- d[v]
    - 처음에는 d[s]=0, d[v]=∞ 로 시작한다.
    - 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] ≥ δ(s,v)를 유지한다.
    - 최종적으로는 d[v] = δ(s,v)가 된다.

- ㅠ[v]
    : s에서 v까지의 최단경로상에서 v의 직전 노드 (predecessor)
    - 그런 노드가 없을 경우 ㅠ[v] = NIL.


기본 연산 : Relaxation


기본 알고리즘
1. 초기화 진행
- 반복 -
2. 모든 에지들에 대해서 relax
- 3. 변화가 없으면 반복 종료 - 

* 이렇게 반복 시에는 최단 경로가 찾아지는가?
* 몇 번 반복해야 하는가?


Bellman-Ford 알고리즘
: 기본 알고리즘과 초기화 하는 부분까지는 똑같은데,
변화 없을때까지 반복하는 것이 아니라, 
반복 회수를 n-1번으로 고정해 놓고 진행한다.
* 음수 사이클이 존재할 때는 false 처리 하도록 진행한다.




댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야