[アルゴリズム]マルチアウトレット
13475 ワード
🚀 マルチアウトレットアルゴリズム
1つの始点から他のすべての頂点への最短パスのアルゴリズム
最短距離を求める場合は、先に求めた最短距離情報を参考にします.
BFSとの違い
BFS BFSは重み付け図で を使用できない.重み付け値はいずれも同じで、所定時間の順序でアクセスするのに適しており、 .
ダエストラは、所定の順序に関係なく である.から、所定の頂点のうち重み付けが最も低い頂点 が選択する.
したがって、は優先キュー を使用するのに適している.ビットで複数のアルゴリズムが実行される場合、O(n^2)の時間的複雑さがある.頂点に比べて、メインラインが少ないほど効率は低下しますが、優先順位キューを使用して改善できます.
1つの始点から他のすべての頂点への最短パスのアルゴリズム
最短距離を求める場合は、先に求めた最短距離情報を参考にします.
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);
}
}
時間の複雑さReference
この問題について([アルゴリズム]マルチアウトレット), 我々は、より多くの情報をここで見つけました https://velog.io/@uchang903/알고리즘-다익스트라テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol