2025/05/21 2

[알고리즘]

Floyd-Warshall Algorithm가중치 방향 그래프 G=(V,E) V={1,2, ..., n}모든 노드 쌍들간의 최단경로의 길이를 구함d^k[i,j]중간에 노드 집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로 길이i.j 사이 어떤 노드도 경유하지 않고 가는 것은 무한대이다 라고 표시합니다. edge가 있으면 edge의 weight로 아니면 무한대로 표시합니다. 노드 i에서 j까지 가는데 1에서부터 n사이의 노드를 지날 수 있고 이것은 i에서 j까지 가는데 어떤 노드를 지나도 상관이 없다라는 것이고 이것이 i에서 j까지 가는 최단경로입니다. i^n[i, j] = 최단경로의 길이다 모든 i.j를 보는 것입니다. wij 자체가 만약 i에서 j로가는 edge가 있..

[알고리즘] Bellman-Ford 알고리즘

노드들을 반복해서 bellman-ford를 만들 수 있는 것에서 아무 에지나 릴렉스하지 않고 특별한 조건을 만족하는 relax에만 만족합니다. 그것이 dijkstra 알고리즘입니다. 초기화는 똑같습니다. 출발 노드만 distance estimator가 0이고 출발을 해서 첫번째 round에서 relax 할 때 distance 값이 최소인 노드를 찾습니다. 최소인 노드로부터 나가는 edge들만 relax합니다. 두번째 round에서는 다시 distance가 최소인 애를 찾는데 dijkstra 알고리즘은 이미 이전 round에서 선택이 되어서 edge들을 두번 선택할 필요는 없습니다. 이 노드의 최단 경로는 현재 노드가 가지고 있는 d[s] = 델타[s,s]입니다.dijkstra는 s만 0이고 나머지는 무한..