경로가없는 노드에 대한 dijikstras 알고리즘

Question

최단 경로 가중치가 무한대 또는 무한대 일 때 Dijkstra 알고리즘이 어떻게 작동합니까 (즉, 경로가 없거나 최단 경로가없는 경우)?

삼각형 부등식 (d [v] = d [u] + w [u, v])는 어떻게 true일까요? 나는 v가 대상 노드라고 가정하고, u는 부모이고 (여기서는 부모가 없다) w는 0이라고 생각되는 가장자리의 무게 (uv)이다.

Answer 1

일부 노드에 부모가없는 경우 은 (u,v)이 존재하는 u이 없습니다.

그러므로 d[v] = d[u] + w[u,v] 단계는 수행되지 않으며 d[v] (무한대로 설정 됨)의 초기 값은 알고리즘이 정지 할 때까지 변경되지 않습니다.

즉, 그래프의 모든 가장자리 (u,v)에 대해 d[v] <= d[u] + w[u,v]은 vacuous true입니다.