데이터 구조에서 Yen의 k-최단 경로 알고리즘

Yen의 k-shortest path 알고리즘은 단일 최단 경로를 제공하는 대신 k 두 번째 최단 경로와 세 번째 최단 경로 등을 얻을 수 있도록 최단 경로를 지정합니다.

A 장소에서 B 장소로 이동해야 하고 A 장소와 B 장소 사이에 여러 경로가 있지만 최단 경로를 찾아야 하는 시나리오를 생각해 보겠습니다. 목적지에 도달하기 위한 시간 복잡도.

예를 들어 이해합시다-

주어진 예를 B의 봉우리가 있는 다리로 생각해 보십시오. 누군가 A에서 C로 다리를 건너고자 한다면 아무도 다리를 건너기 위해 봉우리에 가지 않을 것입니다. 따라서 A에서 C까지의 경로가 조금 더 길어집니다.

최단 경로를 얻는 방법에는 여러 가지가 있습니다. 그러나 우리는 (k-1)까지의 최단 경로를 찾아야 합니다.

k-최단 경로 알고리즘

query= “””
MATCH(start: place{id:source}),*end: Place {Id:destination})
Call algo.kshortestPaths.stream(start,end,10, “distance”)
Yield nodeIDs, path costs, index
Return index.
   [node in algo.getNodeByID(nodeId[1…..-1]) | node.id] aS,
   Reduce (acc=0.0, cost in costs | acc+cost ) as total cost
“””
params= {“source”: Alex,Destination: “US”}
With driver.selection() as session:
  Row session.run(query, params)
  df = pd.DataFrame[dict(record) for record in rows])
pd.set_option(‘max_colwidth’, 100)
display(df)