그래프의 시작 정점에서 모든 정점으로의 최단 경로를 탐색해서 저장하는 알고리즘.
1. 시작 정점에서 모든 정점으로의 최단 경로를 저장할 리스트 혹은 배열 준비한다.
2. 리스트의 값을 모두 무한으로 초기화한다.
3. 현재 방문한 정점에 인접한 정점의 시작 정점으로부터의 경로가 기존 '리스트 혹은 배열'(최단경로) 값보다 작다면 값을 갱신한다.
4. 그래프 내의 모든 정점을 방문할 때까지 3을 반복한다.
다음은 소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include "ShortestPath.h" void Dijkstra(Graph* G, Vertex* StartVertex, Graph* ShortestPath) { int i = 0; PQNode StartNode = { 0, StartVertex }; PriorityQueue* PQ = PQ_Create(10); Vertex* CurrentVertex = NULL; Edge* CurrentEdge = NULL; int *Weights = (int*)malloc(sizeof(int) * G->VertexCount); Vertex** ShortestPathVertices = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount); Vertex** Fringes = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount); Vertex** Precedences = (Vertex**)malloc(sizeof(Vertex*) * G->VertexCount); CurrentVertex = G->Vertices; while (CurrentVertex != NULL) { Vertex* NewVertex = CreateVertex(CurrentVertex->Data); AddVertex(ShortestPath, NewVertex); Fringes[i] = NULL; Precedences[i] = NULL; ShortestPathVertices[i] = NewVertex; Weights[i] = MAX_WEIGHT; CurrentVertex = CurrentVertex->Next; i++; } PQ_Enqueue(PQ, StartNode); Weights[StartVertex->Index] = 0; while (!PQ_IsEmpty(PQ)) { PQNode Popped; PQ_Dequeue(PQ, &Popped); CurrentVertex = (Vertex*)Popped.Data; Fringes[CurrentVertex->Index] = CurrentVertex; CurrentEdge = CurrentVertex->AdjacencyList; while (CurrentEdge != NULL) { Vertex* TargetVertex = CurrentEdge->Target; if (Fringes[TargetVertex->Index] == NULL && Weights[CurrentVertex->Index] + CurrentEdge->Weight < Weights[TargetVertex->Index]) { PQNode NewNode = { CurrentEdge->Weight, TargetVertex }; PQ_Enqueue(PQ, NewNode); Precedences[TargetVertex->Index] = CurrentEdge->From; Weights[TargetVertex->Index] = Weights[CurrentVertex->Index] + CurrentEdge->Weight; } } CurrentEdge = CurrentEdge->Next; } for (int i = 0; i < G->VertexCount; i++) { int FromIndex, ToIndex; if (Precedences[i] == NULL) { continue; } FromIndex = Precedences[i]->Index; ToIndex = i; AddEdge(ShortestPathVertices[FromIndex], CreateEdge( ShortestPathVertices[FromIndex], ShortestPathVertices[ToIndex], Weights[i] )); } free(Fringes); free(Precedences); free(ShortestPathVertices); free(Weights); PQ_Destroy(PQ); } | cs |
'algorithm & data structure > 알고리즘' 카테고리의 다른 글
위상 정렬(topological sort) (0) | 2022.11.29 |
---|---|
스택을 이용한 피보나치 수 구현 (0) | 2022.11.26 |
거듭제곱 알고리즘 구현 (0) | 2022.11.23 |
분리 집합 (0) | 2022.11.23 |
순서도 (0) | 2022.11.16 |