[study] 다익스트라 dijkstra

다익스트라()
graph[][] : 0값이면 간선 없음.
V : 총 노드수
src : 시작 노드번호

1) init:
각 노드에 대한 시작 src 부터의 거리 ( 초기값 MAX/2) : dist[V]
노드 방문여부 (false) : visited[V]
시작노드 거리값 (0) : dist[src] = 0

2) loop : V-1 ( 시작src 는 제외하므로 dist=0)

2-1)가장 가까운 거리에 있는 node (이미 방문한 노드는 제외) : minimal dist[i] && !visited[i] -> idx = i

2-2) 그 노드를 방문처리함

2-3) 모든 거리에 대해 더 가까워지는 거리를 찾아 (이미 방문한 노드 제외, 간선이 있는 경우만) : dist[i] > dist[idx]+graph[idx][i]
값 대체

#########################################
int graph[][]

void dikstra(int src){
int V=9;//count
boolean visited[V]; // false
int dist[V]; Arrays.fill(dist,Max/2) : Max/2

dist[src]=0

for(0:V-1){
// get min node
distance=Max/2, nodeidx : -1
for(i:V){ if(!visited[i]&&distance>dist[i]){ distance=dist[i]; nodeidx = i } }

visited[nodeidx]=true

for(i:V){ if( !visited[i] && graph[idx][i]!=0 && dist[i]> dist[idx]+graph[idx][i]){ dist[i] = dist[idx]+graph[idx][i]}
}

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중


%d 블로거가 이것을 좋아합니다: