アルゴリズム-マルチアウトレット

いつも書くのを忘れて...
1つの頂点からすべての頂点までの最小コスト距離を求めます
ex)最安値で置き、最短時間で目的地に到着するなど

たじゅう

しょきじょうたい

0番ノードはINFではなく0に初期化できます

頂点を基準として設定

0ノードベース


0番ノードに隣接してリフレッシュされたノードに基づきます.
隣接ノードのウェイト値を再参照

1ノードベース

ウェイト値は、1ノードの隣接する2ノードに計算されます.
重みを1ノード2+ここから2ノード1=3へ
dist[2]に格納されている値は6であり、リフレッシュが必要である
また、1ノードから隣接する3ノードまでの重みを計算してください.
重みを1ノード2+ここから3ノード6=8へ
dist[3]に格納されている値はINFであり、リフレッシュが必要である

更新された2番目のノードは、3番目のノードに従って同じナビゲーション

を繰り返す

インプリメンテーション

int[] dist // 최단경로 거리 담고있는 배열
int[][] adj // 인접행렬 정보(단방향, 양방향에 따라 다름)
Queue q // 탐색해야하는 노드 번호 offer하는 큐

adj를 기반으로 1차원 dist 배열 초기화 // 탐색하고자 하는 노드는 0위치로 초기화, 나머지는 INF

q.offer(탐색하고자 하는 노드 번호)
while(!q.isEmpty()){
	q.poll() //큐에서 노드번호 꺼내고
    꺼낸 번호에서 인접한 노드들을 0~N-1 까지 반복문으로 탐색
    
    만약
    dist[i] = dist[i] < (dist[꺼낸 노드] + adj[꺼낸 노드][i]) ? dist[i] : (dist[꺼낸 노드] + adj[꺼낸 노드][i])
    라면, dist[i] 갱신하고, queue 다음 탐색 노드 값으로 넣어줌
    
    
}