Algorithms

Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안하였고, Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안하였다. 그래서 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워샬 알고리즘이라 한다. 플로이드 알고리즘의 시간복잡도는 O(n3)으로 다익스트라 알고리즘을 n번 사용할 때의 시간복잡도와 동일하지만 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다. 플로이드 알고리즘은 모든 점을 경유 가능한 점들로 고려하면서 모든 쌍의 최단 경로의 거리를 계산한다. 이것은 점 1∼n까지의 모든 점을 경유 가능한 점들로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산하는 것이다. 다음과 같은 입출력이 가능한 코드를 ..

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Dijkstra { class Program { static string[] city = { "서울", "천안", "원주", "강릉", "논산", "대전", "대구", "포항", "광주", "부산" }; static int V = 10; // 도시 갯수 static bool[] spt = new bool[V]; // shortest path tree, // true if 버텍스가 spt에 포함되면 static int[] D = new int[V]; // 각 도시의 최단경로 stati..

using System; namespace Prim { internal class Graph { static int MAX = 100; // 최대 버텍스 수 static int INF = 999; int V = 0; // 그래프 안의 버텍스의 수(파일에서 읽어옴) string[] vertex = new string[MAX]; int[,] adj = new int[MAX,MAX]; // 해당 index의 버텍스 이름을 가져오기 public string GetVertex(int i) { return vertex[i]; } int MSTWeight = 0; internal void Prim(int start) { bool[] selected = new bool[MAX]; int[] dist = new int[..

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows; namespace ClosestPair { class PointPair { public Point P1 { get; set; } public Point P2 { get; set; } public double Dist { get; set; } public PointPair(Point p1, Point p2, double dist) // 생성자 { P1 = p1; P2 = p2; Dist = dist; } } }

using System; using System.Threading; using System.Windows; using System.Windows.Controls; using System.Windows.Media; using System.Windows.Shapes; namespace SortWithGraph { public partial class MainWindow : Window { static int MAX = 1000000; int[] a = new int[MAX]; int N = 0; Thread t1; private bool timeFlag; public MainWindow() { InitializeComponent(); } private void BtnCreate_Click(object sen..