그래프의 시작 정점에서 모든 정점으로의 최단 경로를 탐색해서 저장하는 알고리즘.

 

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

+ Recent posts

티스토리툴바