C++ Dijkstra 알고리즘 - 가장자리 이름/유형 인쇄

Question

현재 Dijkstra의 최단 경로 문제를 해결하고 있습니다. 이 프로젝트에서 특별한 것은 없지만 한 꼭지점에서 다른 꼭지점으로 가장자리 유형을 인쇄해야한다는 것 외에는 알고리즘이 표준입니다 (쌍 세트로 구현).

4 개의 정점과 5 개의 가장자리가 있다고 상상해보십시오. v1과 v2를 연결하는 두 개 이상의 에지가 존재하도록 한 쌍의 정점 p (v1, v2)가 존재합니다. 예를 들어 런던에서 파리까지 거리를 찾고 싶습니다. 우리는 둘 다 자동차로 운전할 수 있다는 것을 알고 있습니다. (한 가지 유형의 가장자리) 비행기 표 (다른 유형의 가장자리)를 살 수 있습니다. 내가 원하는 것은 가장자리의 유형을 인쇄하는 것입니다.

예 : 런던에서 파리까지가는 두 가지 방법이 있습니다. 런던 -> 칼레 -> 파리, 차로 최소 5 시간, 런던 -> 파리, 비행기로 최소 시간 1 시간.

최소 시간이나 최소 거리를 인쇄하는 방법, 경로를 인쇄하는 방법 등은 잘 알고 있습니다.하지만 '비행기 별'또는 '자동차'와 같은 가장자리 유형 (교통 유형)은 어떻게 인쇄 할 수 있습니까? '? 여기에 내가 뭘하려 :

struct neighbor { 

int target_vertex; 
double weight; 
int type; 
// for type: 0 - car 
// 1 - bus 
// 2 - plane 

}; 

하지만 여전히, 내가 알아낼 수, 최단 경로를 계산하는 동안 그 가장자리 '유형'을 저장하는 것입니다 방법에 대해 설명합니다. 여기

코드 : 이미이 정보는, 그것이 prev_type[x] 배열에 저장 한 https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

Answer 1

한 도시에서 다른 도시로 가능한 모든 상황을 미리 정의하여 문제를 해결했습니다 (기본적으로 모든 도시 조합).

if (choice == 1) { 
    switch (from) { 
     case 0: { 
      if (to == 1) std::cout << " by foot "; 
      if (to == 2) std::cout << " by foot -> by bus "; 
      if (to == 3) std::cout << " by air "; 
      break; 
     } 
     case 1: { 
      if (to == 0) std::cout << " by foot "; 
      if (to == 2) std::cout << " by bus "; 
      if (to == 3) std::cout << " by bus -> by car "; 
      break; 
     } 
     case 2: { 
      if (to == 0) std::cout << " by bus -> by foot "; 
      if (to == 1) std::cout << " by bus "; 
      if (to == 3) std::cout << " by car "; 
      break; 
     } 
     case 3: { 
      if (to == 1) std::cout << " by car -> by bus "; 
      if (to == 2) std::cout << " by car "; 
      if (to == 0) std::cout << " by air "; 
     } 
    } 

= 시작 도시

to = 우리가 향하고있는 목적지.

나는 해결책이 최선이 아니라고 확신하지만 소수의 노드와 모서리가있는이 특별한 경우에는 적용 가능합니다.

Answer 2

. 이 배열에는 최종 노드 t에 도달하는 데 사용 된 transport 유형이 포함되어 있습니다. 상위 노드 또는 현재 노드 노드에 도달 한 노드 노드를 기억하는 어레이 prev[]과 함께 작동합니다. 따라서 t (최종 노드)에서 시작하여 prev[t]으로 전화하여 부모를 얻고 prev_type[t]에 t에 도달하는 데 사용 된 전송 유형이 포함됩니다. 이 방법을 계속하면 s (시작) 노드에 도달 할 때까지 되돌아갑니다.