graph algorithms

[seoyeong200]

description

graph types - direction, weight, cycle, connection 유무에 따라 그래프 종륲 구분 graph traversals - BFS, DFS shortest path algorithms - Dijkstra, Bellman Ford, Floyd minimum spanning tree - prim, kruskal

[seoyeong200]

graph traversals

[seoyeong200]

shortest path

dijkstra & bellman-ford vs floyd

• dijkstra & bellman-ford : from single node to every node
• floyd : between all pairs of nodes

dijkstra vs bellman-ford

• dijkstra : 음수 간선 없는 가중치 그래프
• bellman-ford : 음수 간선 존재하는 가중치 그래프

Dijkstra's algorithm

• find shortest path between nodes in a weighted graph
• maintain a set of tentative distances to every node, iteratively updating these distances based on the actual distances found
• 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 때 사용하는 알고리즘. 다음 방문 노드의 선정 기준이 방문하지 않은 노드 중 가장 비용이 적은 노드 이다.

main points

• SPT(shortest path tree) 생성
• 인접행렬 set 2개
  • SPT에 포함된 정점들 set
  • SPT에 포함되지 않은 정점들 set

• 1753. 최단경로

[seoyeong200]

Bellmand Ford

• find the shortest paths in weighted graph, even with opposing weight edges
• iteraively relaxing the edges in the chart

1. distance 배열 inf 로 초기화, start node는 0으로 초기화
2. repeat v-1 times - 각 (u, v) 간선에 대해서 (weight w) dist[u]+w<dist[v] 면 dist[v]=dist[u]+w
3. negative weight check - 2번 단계에서 distance 감소하면 negative-weight cycle 존재

[seoyeong200]

Floyd Warshall Algorithm

• 다른 모든 정점으로 가는 최단경로를 모두 구하는 알고리즘
• 방향성이 있을 때 사용하는 알고리즘.
• 핵심은 정점 개수 n이라 했을 때 n을 삼중으로 돌면서 i 에서 k를 거쳐 j로 가는 경로가 더 최소인지를 파악해보면서 가장 작은 값들만 distance 든 graph 든 n*n배열에 업데이트 해나가는 것이다.

그래서 기본적으로는 알고리즘이 아래와 같은 형태다.

# create graph array : N*N array, graph[i][j] = i에서 j로 가는 최단경로
for i in range(n): # proxy vertex
    for j in range(n): # start vertex
        for k in range(n): # end vertex
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])