그래프의 최소 경로는 무엇입니까?

Question

그래프 이론에서, 최소 거리 (Dijkstra의 알고리즘이 찾은)와 최소 경로 (그것이 무엇인지 잘 모르겠다)의 구분은 무엇입니까?

Answer 1

최소 경로는 가로 질 때 두 모서리 사이의 가장 작은 거리를 덮는 가장자리 세트입니다. 최소 거리는 최소 경로의 가장자리 사이의 거리의 합계입니다.

Answer 2

거리는 스칼라입니다. 숫자. 경로는 정점/에지 쌍의 목록입니까?

Answer 3

최소 거리 = 가장자리 가중치의 최소 합. 최소 경로 = 최소 가장자리.

IE // 밴쿠버에서 토론토로 비행기를 타고 밴쿠버에서 캘거리, 레지나까지, 위니펙으로 비행하는 것이 더 짧은 거리이지만 더 짧은 길입니다.

편집 : 내 생각에 뒤집어.

Answer 4

나는 100% 확실하지 않지만 정점 A에서 vertex B까지 최소 거리 경로를 가로 질러 방문한 정점 목록이 될 것 같습니다.

Answer 5

소스와 싱크가있는 네트워크 범위 내 에서이 질문에 답하겠습니다. 경로가 가장자리 세트로 정의되는 가장 짧은 경로와 최소 경로를 구별하고 싶습니다.

가장 짧은 경로는 해당 거리가 가장 짧은 소스에서 싱크로의 경로입니다. 최소 경로는 소스를 싱크대에 연결하는 경로 일 수 있습니다.

i) 사이클이 포함되어 있지 않습니다. 그리고

ii) 경로에서 가장자리를 제거한다는 것은 더 이상 소스와 싱크 사이에 연결이 없음을 의미합니다.

Answer 6

최소 거리는 최소 경로와 동일합니다.