URL의 최단 경로 알고리즘

Question

두 URL 간의 최단 경로를 찾는 데 문제가 있습니다. 우리가 제공하는 .csv는 쉼표로 구분 된 많은 웹 사이트를 나열합니다. 각 웹 사이트는 해당 페이지의 하이퍼 링크 내에있는 다음 웹 사이트에 액세스 할 수 있습니다. 예를 들어 파일이 espn.com, espn.com/nba, espn.com/nbaschedules을 읽으면 espn.com에서 nba 페이지로, nba 페이지에서 nba 스케줄로 이동할 수 있습니다. 내 직업은 한 웹 사이트에서 다른 웹 사이트로 이동하는 데 필요한 클릭 수를 가장 적게 찾는 것입니다. 지금까지 파일을 저장 한 방법은 다음과 같습니다. 내가 사용하고있는 것은 저장을위한 STL unordered_map이다.

내 질문에 올바르게 저장 했습니까? Dijkstra의 알고리즘이나 광범위한 우선 검색을 사용해야합니까?

Answer 1

아마도 Dijkstra의 알고리즘을 사용해야 할 것입니다. 또한 모든 데이터를 일종의 그래프 구조에 저장해야합니다 (예 :

struct graph_node { 
    vector<graph_node*> neighbours; 
    string url; 
} 

map을 사용하여 모든 value-> graph_node 포인터를 저장할 수도 있습니다. 그런 다음 Dijkstra의 알고리즘을 사용하여 그래프를 작성한 후 최단 경로를 찾습니다.

Answer 2

Dijkstra 's algo는 하이퍼 링크 간 전환 비용이 다른 경우에만 효율적입니다.

그래서 BFS를 선호합니다.

O (V) O보다 더 ((V + E) 로그 (V + E)) {V-정점 E-가장자리}

그것은 IDS의 인접리스트의 그래프를 저장하는 것이 낫다 벡터 < 벡터 < 문자열>>에 저장하는 대신 벡터 < 벡터에 저장하는 대신 int>>를 사용하십시오. 배열을 사용하여 ID의 URL을 식별하십시오.