Taehyeon-Kim/SwiftAlgorithm

Shortest path algorithm

Closed this issue · 1 comments

그래프

  • Vertex(정점) : 노드
  • Edge(간선)

최단 경로(Shortest path)

  • 노드 사이에 존재할 수 있는 모든 경로 중의 가장 짧은 경로를 최단 경로라고 할 수 있다.
  • 단, 가중치 그래프와 비가중치 그래프에서 차이가 존재할 수 있는데 가중치 그래프에서 최단 경로는 엣지의 가중치의 합이 가장 적은 경로가 최단 경로이고, 비가중치 그래프에서 최단 경로는 엣지의 갯수가 가장 적은 경로가 최단 경로이다.

최단 경로 알고리즘

  • BFS : 비가중치
  • Dijkstar : 가중치