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


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

  • 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)の時間的複雑さがある.頂点に比べて、メインラインが少ないほど効率は低下しますが、優先順位キューを使用して改善できます.