자료구조 | Shortest Path and Activity Network

Shortest Path Finding

• Dijkstra Algorithm

• Floyd–Warshall algorithm

• Transitive Closure Matrix

• Activity Network

---

Shortest Path Finding (1~20)

<정의>

Shortest Path finding은 weighted Digraph에서 최적의 path를 찾는 문제다. 

이때 path length는 지나온 path에서 각 edge의 weight를 합해서 구한다.

 source vertex -> destination vertex라는 용어도 사용한다. 

 

<Type>

shortest path는 3 가지 타입이 있다.

첫째는 vertex u에서 vertex v로 가는 경로를 찾는 "single source, single destination"이다. 

둘째는 vertex u에서 향할 수 있는 모든 경로를 찾는 "single source, all destination"이다. 

마지막은 모든 vertex에서 다른 모든 vertex로 향하는 경로를 찾는 "All paths"이다. 

 

<그리디 알고리즘>

그리디 알고리즘은, 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 기법을 말한다.

이렇게 선택하는 방식은 local optimization이라서 보완적으로 사용되어야 한다. *_*

 

그리디 알고리즘을 이용하면, 3가지 단계를 따라 최적의 경로를 찾아낼 수 있다. 

step 0. 출발점(source vertex)에서 가장 저렴한 인접 edge로 이동한다.

step 1. 다음 edge는 [1] 아직 방문하지 않은 것 중에서 [2] 가장 저렴한 것으로 고른다.

step 2. 목적지에 반복할 때까지 step 1을 반복한다. 

 

---

Single source all destination

need to generate up to n paths ( source == destination인 경우도 포함시킨다)

 

• Dijkstra Algorithm

> 목표 : length가 길어지는 순서대로 n 개의 path를 구축한다. 

> 전제 : edge cost(path length) >= 0이다. 

step 0. 처음 시작은 source vertex == destination vertex로 하고, length는 0이다. 

step 1. source vertex에서 인접한 다른 vertex로 나아가면서 최적의 경로를 찾아낸다. 

 

> 예제

DONE : 1, 2, 3, 4, 5, 6, 7

1 : 0

1-> 3 : 2

1->3->5 : 5

1->2 : 6

1->3->5->4 : 9

1->3->6 : 10

1->3->6->7 : 11

 

next shortest path is the shortest one edge extension of an already generated shortest path

shortest paths ffrom the source to all other destination

 

> DataStructure과 연결하기

d[i] = source가 i까지 도달하는 데 걸리는 거리

p[i] = i에 도달하기 전 vertex

 

the next shortest path is to an as yet unreached vertex for which the d[] value is least

p[i] be the vertex just before vertex i on the one edge extension to i

 

 

=> 시간 복잡도

O(n) : 다음 vertex를 선정

O(n) : adjacency matrix를 이용해서 d[], p[] value를 업데이트(n번 반복)

selection and update done once for each vertex to which a shortest path is found

total time : O(n^2)

* 만약에 min dist를 선택하는 데 heap이 사용되면, O(nlogn)도 될 수 있다. 

 

class Node:
    def __init__(self, node, weight):
        self.data = node
        self.weight = weight
class ShortestPath:
    def __init__(self):
        self.graph = {}
        self.visit = []
        self.dist = {}
        self.prev = {}
        self.min_list = {}
    def create(self, v, dest, weight):
        node = Node(dest, weight)
        if v not in self.graph:
            self.graph[v] = []
        self.graph[v].append(node)
    def pick_min_dist(self):
        temp = []
        for v, cost in self.min_list.items():
            temp.append((cost, v))
        temp = sorted(temp)
        cost, v = temp.pop(0)
        print("Next min cost vertex is", v)
        self.min_list.pop(v)
        return v
    def dijkstra(self, v):
        if v not in self.visit:
            self.visit.append(v)
        else:
            return
        if v not in self.graph:
            print("End of search")
            return
        for node in self.graph[v]:
            vertex = node.data
            cost = node.weight
            if vertex not in self.dist or cost + self.dist[v] < self.dist[vertex]:
                self.dist[vertex] = cost + self.dist[v]
                self.prev[vertex] = v
                self.min_list[vertex] = cost + self.dist[v]
        print(self.graph)
        v = self.pick_min_dist()
        self.dijkstra(v)

g = ShortestPath()
for start,dest,weight in [(1,2,6),(1,3,2),(1,4,16),(1,7,14),(2,4,5), \
(2,5,4),(3,2,7),(3,5,3),(3,6,8),(4,7,3),(5,4,4),(5,7,10),(6,7,1)]:
    g.create(start, dest, weight)
g.dist[1] = 0
g.prev[1] = None
g.dijkstra(1)

 

---

All sources and All destinations

모든 vertex pair에 대해서 최단 거리를 찾아주는 문제

cost matrix를 만든다. 

 

• cost matrix : A^k, A^-1

<A^k>

A^k 행렬에서 A^k[i][j]는 i에서 j까지 0~k개의 vertices만을 거치고 가는 데 드는 비용을 의미한다. 

A^k[i][j]는 A^k-1[i][j]에 의해 결정된다. 

A^k[i, j] = min{A^k-1[i,j], A^k-1[i,k] + A^k-1[k,j]} # 이때 후자는 k를 경유하는 새로운 경우를 말한다. 

 

<A^-1>

A^-1[i][j] = cost[i][j]

edge weight를 기록하기 위한 행렬. edge가 없으면 infinite value를 저장한다

 

 

• Floyd–Warshall algorithm(29~30)

shortest path between all pairs of vertices

negative edges allowed

 

let dist be a |V|×|V| array of minimum distances initialized to ∞
for each vertex v: # array를 초기화
	dist[v][v] = 0  
for each edge (u, v):
	# weight를 업데이트해준다. 
	dist[u][v] = w(u, v) # the weight of the edge (u, v)
for k from 0 to |V|-1: # vertex : 0 .. n-1
	for i from 0 to |V|-1:
		for j from 0 to |V|-1:
			if dist[i][j] > dist[i][k] + dist[k][j]:
            	# 만약에 다른 길로 우회하는 경로가 더 저렴하다면? 
				dist[i][j] = dist[i][k] + dist[k][j] 
end if

 

• Transitive Closure Matrix(30~31)

 

<Transitive closure matrix 이행적 폐쇄 행렬>

A+

i, j 사이에 path가 있으면, A+[i][j] = 1,

없으면 0

 

<reflexive transitive closure matrix 반사이행적 폐쇄 행렬>

A*

TCM을 변형해서 나 자신에게 돌아오는 경로를 허용하는 행렬

diagonal element는 1

 

---

• Activity Network(32~42)

Activity on Vertex AOV : 정점 작업 네트워크

테스크간의 선행관계를 나타내는 digraph

 

• Topological sort