中庸 中庸

Shortest Path 를 구하는 대표적인 Alogorithm 으로는 Dijkstra Algorithm 이 있었습니다. Dijkstra 알고리즘의 key lemma 는 다음과 같았습니다. Dijkstra Algorithm 에서 (아직 방문 안 한 vertex 들 중) vertex s 에서부터의 shrotest path 길이가 가장 짧은 vertex 를 v라 하면 그 길이는 실제 s에서 v로의 shortest path 길이와 같다. 위 key lemma 는 weight 가 negative 인 edge 가 존재할 경우 성립하지 않습니다. 그 이유는 다음과 같습니다. 그렇다면 negative edge 가 있는 경우에도 동작하는 Shortest path 를 구하는 Algorithm은 무엇이 있을까요? The ..