다익스트라(Dijkstra)란?

다익스트라는 최단경로 알고리즘이다. 이때 최단경로란 특정 노드에서 다른 노드까지의 최단 경로를 의미한다.

다익스트라 구현

비용 배열(걸리는 시간or거리 같은 비용)과 방문 배열(방문했는지 안했는지)을 이용한다. 디폴트값으로 비용 배열에는 무한대값을 모두 넣고, 방문 배열에는 모두 방문하지 않았다(False)는 데이터를 넣는다. 다음으로 시작노드를 정하고 해당 노드에 대해 방문 배열은 True, 비용 배열은 0값으로 갱신한다. 이후 시작 노드로부터 연결된 노드에 대한 최소 비용을 알아내((지금까지 총 비용 + 다음노드로 비용) vs 현재비용배열에서 최소비용) 비용배열을 갱신해주고, 방문 배열에 방문을 하지 않았다고 적혀있으며, 비용이 가장 적게 드는 노드로 이동을 계속한다.

플로이드 와샬이란?

플로이드 와샬은 최단경로 알고리즘이다. 이때 최단경로란 모든 노드를 방문하는 최단 경로를 의미한다. 이때 방문이란 단지 전체 경로에 연결만 되어있으면 방문했다고 본다. 간단히 말하면 플로이드 와샬은 전체 노드를 연결할 수 있는 최단 비용의 경로들을 의미한다.

플로이드 와샬 구현

비용 배열(걸리는 시간or거리 같은 비용), 방문 배열(방문했는지 안했는지)을 이용한다. 디폴트값으로 비용 배열에는 무한대값을 모두 넣고, 방문 배열에는 모두 방문하지 않았다(False)는 데이터를 넣는다. 다음으로 시작노드를 정하고 해당 노드에 대해 방문 배열은 True, 비용 배열은 0값으로 갱신한다. 이후 시작 노드로부터 연결된 노드에 대한 최소 비용을 알아내(다음노드로 비용만 vs 현재비용배열에서 최소비용) 비용배열을 갱신해주고, 방문 배열에 방문을 하지 않았다고 적혀있으며, 비용이 가장 적게 드는 노드로 이동을 계속한다.