[TIL] 128 [C#] 플로이드-워셜 알고리즘 (Floyd-Warshall) 최단경로

---

Floyd-Warshall 플로이드-워셜

---

플로이드-워셜 알고리즘 (Floyd-Warshall)

모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

예시

class Program
{
    static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput());

        int users = 5;
        int[,] graph = new int[users + 1, users + 1];
        int INF = 1000000;


        // 1. 자기자신=0, 나머지 INF = 무한대(적당한크기)(Int,maxvalue는 X)
        for (int i = 1; i <= users; i++)
        {
            for (global::System.Int32 j = 1; j <= users; j++)
            {
                graph[i, j] = (i == j) ? 0 : INF;
            }
        }


        // 2. 무방향 그래프 간선 
        // 입력
        // 1 3
        // 1 4
        // 4 5
        // 4 3
        // 3 2
        for (int i = 0; i < 5; i++)
        {
            int[] edge = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
            graph[edge[0], edge[1]] = 1;
            graph[edge[1], edge[0]] = 1;
        }


        // 3. 플로이드-워셜
        // i -> j 로 가는 최단거리 = i=>?=>j  경우의수의 최소값 
        for (int k = 1; k <= users; k++)
        {
            for (int i = 1; i <= users; i++)
            {
                for (int j = 1; j <= users; j++)
                {
                    graph[i, j] = Math.Min(graph[i, j], graph[i, k] + graph[k, j]);
                }
            }
        }


        // 출력
        for (int i = 1; i <= users; i++)
        {
            for (global::System.Int32 j = 1; j <= users; j++)
            {
                sw.Write(graph[i, j]);
            }
            sw.WriteLine();
        }
        sw.Flush();sw.Close();
    }
}

1. 초기화

// 1. 자기자신=0, 나머지 INF = 무한대(적당한크기)(Int,maxvalue는 X)
for (int i = 1; i <= users; i++)
{
    for (global::System.Int32 j = 1; j <= users; j++)
    {
        graph[i, j] = (i == j) ? 0 : INF;
    }
}

2. 간선 입력

// 2. 무방향 그래프 간선 
// 입력
// 1 3
// 1 4
// 4 5
// 4 3
// 3 2
for (int i = 0; i < 5; i++)
{
    int[] edge = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
    graph[edge[0], edge[1]] = 1;
    graph[edge[1], edge[0]] = 1;
}

3. 플로이드 - 워셜

// 3. 플로이드-워셜
// i -> j 로 가는 최단거리 = i=>?=>j  경우의수의 최소값 
for (int k = 1; k <= users; k++)
{
    for (int i = 1; i <= users; i++)
    {
        for (int j = 1; j <= users; j++)
        {
            graph[i, j] = Math.Min(graph[i, j], graph[i, k] + graph[k, j]);
        }
    }
}

x -> y 로의 최단 경로

---

잡담, 일기?

플로이드-워셜 알고리즘 최단 경로를 알 수 있다..

---