[アルゴリズム]マルチアウトレット

🚀 マルチアウトレットアルゴリズム

1つの始点から他のすべての頂点への最短パスのアルゴリズム

最短距離を求める場合は、先に求めた最短距離情報を参考にします.

BFSとの違い
BFS

BFSは重み付け図で

を使用できない.

重み付け値はいずれも同じで、所定時間の順序でアクセスするのに適しており、

.
ダエストラ

は、所定の順序に関係なく

である.

から、所定の頂点のうち重み付けが最も低い頂点

が選択する.
したがって、

は優先キュー

を使用するのに適している.

 class Graph
    {
        const int INF = int.MaxValue;   //두 정점 사이에 간선이 없을 경우 가중치

        int[,] arr = {
                {0, 7, 6, INF, 8, 14},
                {7, 0, 13, 15, INF, INF},
                {9, 10, 0, 11, 6, 2},
                {INF, 15, INF, 0, 6, INF},
                {INF, INF, INF, 6, 0, 8},
                {14, INF, 2, INF, 9, 0}
            };


        // 다익스트라 알고리즘
        public void Dijikstra(int start)
        {
            int n = 6;
            bool[] visit = new bool[n];     //방문 여부 배열
            int[] distance = Enumerable.Repeat(Int32.MaxValue, 6).ToArray();    //현재 최소 가중치들을 담는 배열

            distance[start] = 0;

            while (true)
            {
                int closet = Int32.MaxValue;    //현재 최소 가중치
                int now = -1;   //가장 가까운 가중치를 가진 인덱스

                // 현재까지의 distance를 바탕으로 방문해야 할 정점을 찾기
                for (int i = 0; i < n; i++)
                {
                    if (visit[i] == true) // 방문한 적 있거나
                        continue;
                    if (distance[i] == Int32.MaxValue || distance[i] > closet)  // 찾은적 없거나 | 기존 후보보다 멀리 있으면 continue 
                        continue;

                    closet = distance[i];
                    now = i;
                }

                //다음 방문해야할 정점이 없다면 break
                if (now == -1)
                    break;

                //방문
                visit[now] = true;

                // 최소 distance 갱신하기
                for (int next = 0; next < 6; next++)
                {
                    //간선이 없거나
                    if (arr[now, next] == INF)
                        continue;

                    //방문한적 있다면 continue
                    if (visit[next])
                        continue;

                    // 새로 발견된 최단 거리가 기존에 있던 최단 거리보다 작다면 갱신
                    int nextDist = distance[now] + arr[now, next];

                    if (nextDist < distance[next])
                        distance[next] = nextDist;
                }
            }
        }
    }


    class Program
    {
       
        static void Main(string[] args)
        {
            Graph graph = new Graph();
            graph.Dijikstra(0);
        }
    }
    

時間の複雑さ

ビットで複数のアルゴリズムが実行される場合、O(n^2)の時間的複雑さがある.頂点に比べて、メインラインが少ないほど効率は低下しますが、優先順位キューを使用して改善できます.