11404-플로이드 #AllPairsShortestPath #자료구조의소팅 #qsort사용법

최단거리 알고리즘에는 종류가 참 많다. 그 중 All-Pairs-Shortest-Path 로는 (1)매트릭스곱, (2)플로이드-와샬, (3)존슨 세가지를 배웠었다.

사실 이 세가지 알고리즘은 아직도 잘 이해가 안간다. (이번 문제는 플로이드-와샬로 푸는 문제였는데, 그냥 다익스트라를 n회 돌렸다.)

어디에서든 Dijkstra가 최고인 것 같다. 

Bellman-Ford(Single Source Shortest Path)

-한점->모든점Single Source Shortest Path

-노드의 수V 횟수만큼, 모든 엣지E를 릴랙스한다. (최적화: 업데이트된 노드에 대해서 릴렉스)

-네거티브 weight cycle이 있는지 확인해준다

-positive cycle이 있어도 된다.

-negative edge가 있어도 된다.

-O(VE)

Dijkstra(Single Source Shortest Path)

-min-heap: O((V+E)lgV)

-fibo-heap: O(VlgV + E)

Johnson's(All Pairs Shortest Path)

-모든점->모든점

-BellmanFord를 돌려서 negative cycle이 있는지 확인후 모든 점에 대하여(;;;) Dijkstra 실행 ????

-V^2logV + VE (fibo-heap)

<Array의 Sort>

qsort(array 시작주소, sorting 할 element 개수, sizeof(elemen의 type), compareMyType함수(☆))  사용법

#include <cstdlib>

qsort에 들어가는 compareMyType 함수는 다음과 같이 정의되어야 한다. const void*로 받아서 본인의 타입으로 다시 typecasting해주고 어느쪽이 큰지 방향을 int를 리턴해주는 것이다.

int compareMyType (const void * a, const void * b)

{

  if ( *(MyType*)a <  *(MyType*)b ) return -1;

  if ( *(MyType*)a == *(MyType*)b ) return 0;

  if ( *(MyType*)a >  *(MyType*)b ) return 1;

}

<Vector/List의 Sort>

sort(myNode.begin(), myNode.end(), Comparator) 사용법

bool Comparator(Node n1, Node n2){

return (n1.number > n2. number)

} //n1 - n2 순서로(내림차순) 정렬

<Priority Queue의 Sort>

struct/class 내의 오퍼레이터 bool operator<(const typeName& rhs) const 오버로딩 하는법

struct Edge { //minHeap

int v, w;

Edge(int _v, int _w) : v(_v), w(_w) {}

bool operator<(const Edge& rhs) const {

return w < rhs.w;

}

};

struct _Edge { //maxHeap

int v, w;

_Edge(int _v, int _w) : v(_v), w(_w) {}

bool operator<(const _Edge& rhs) const {

return w > rhs.w;

}

};