A modified Label Correcting Algorithm (FIFO , Deque) with Python
Label correcting algorithm은 single source shortest path problem 입니다. Label correcting algorithm 은 dijkstra algorithm과 달리 cost 가 음수일 때도 iteration 을 통해 노드간 최소 거리 (cost)를 구할 수 있습니다. negative cost가 있는 부분에서 cycle 이 발생한다면 반복이 진행될 때 unbounded로 낮아지기 때문에 graph의 negative cost가 있는 부분에서 cycle이 발생하면 안됩니다.
기존 Label Correcting Algorithm은 반복 회수가 n-1 회( n = number of nodes ) 진행되나, modified label correcting algorithm은 LIST를 이용하여 반복 회수를 줄여주게 됩니다.
1. Graph 및 cost 생성
- cost는 모두 정수
- -10 <= negative cost < 0 , 1<= positive cost < 20
- cycle 발생 X
- arcs = ( i node, j node, cost from i node to j node )
# cycle check fuction : DFS 통해 확인
def cycle_check( arcs, stack, edge ) :
if edge in stack :
global IsCycle
IsCycle = True
return True
stack.append( edge )
successive_edges = [ arc for arc in arcs if arc[0] == edge[1] ]
for edge in successive_edges :
cycle_check( arcs, stack, edge )
stack.pop()
return IsCycle
def get_node_arc_set( total_num_arcs, total_num_nodes, negative_ratio , negative_cost_range, positive_cost_range ) :
num_arcs = 0
arcs = []
negative_cost = np.random.choice( negative_cost_range , int( total_num_arcs * negative_ratio) )
positive_cost = np.random.choice( positive_cost_range , int( total_num_arcs * (1- negative_ratio)) )
costs = np.concatenate( [negative_cost,positive_cost] )
np.random.shuffle(costs)
while num_arcs != total_num_arcs :
i, j = np.random.choice( np.arange(0, total_num_nodes ) , 2 , replace = False) # 랜덤으로 서로 다른 두 노드 i,j 선택
if (i,j) in list(map( lambda x : x[:2] , arcs ) ) : # 이미 존재하는 arc 뽑았을 경우 continue
continue
temp_arcs = copy.deepcopy(arcs)
temp_arcs.append( (i,j) )
global IsCycle
IsCycle = False
IsCycle = cycle_check( temp_arcs, [] , (i,j) ) # 전역 변수 통해 Cycle 이 있는지 아닌지 확인
if IsCycle == True:
continue
else : # (i,j) 를 arcs에 추가했을 때 Cycle이 발생하지 않으므로 arcs 에 (i,j)를 추가 ( arcs := temp_arcs )
arcs.append( (i,j, costs[num_arcs]) )
num_arcs += 1
return arcs
2. Generic modified label correcting algorithm
LIST is the list of all arcs that might violate their optimality conditions( = d(j) > d(i) + c_ij ).

LIST에 arc를 어떻게 담을지에 따라 구체적인 구현이 다른데, 크게 FIFO ( First In First Out ) 과 Dequeue ( Double-ended Queue ) 를 통해 구현 합니다. 다음은 FIFO 와 Dequeue를 통한 구현을 보도록 하겠습니다.
3. FIFO
LIST 로 Queue를 이용하고 담는 방식으로 First In First Out 을 사용하는 방식입니다. 수도 코드는 다음과 같습니다.

Code 는 다음과 같습니다.
def init_FIFO(s, total_num_nodes ) :
inf = 99999
d = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
pred = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
q = [s]
return q, d, pred
def MLC_FIFO( q, d, pred, arcs ):
while q != [] :
i = q.pop(0)
i_arcs = [ arc for arc in arcs if arc[0] == i]
for arc in i_arcs :
j = arc[1] ; cost = arc[2]
if d[j] > d[i] + cost :
d[j] = d[i] + cost
pred[j] = i
if j not in q :
q.append(j)
return d, pred
4. Dequeue
LIST로 Dequeue를 사용하고 j node가 LIST에 없을 때 j node가 예전에 LIST에 존재하지 않았으면 j를 LIST 맨 뒤에 j node를 추가하고 j node가 예전에 존재했었으면 LIST 맨 처음에 j node를 추가 합니다. 수도 코드는 다음과 같습니다.

코드는 다음과 같습니다.
def init_Deque(s, total_num_nodes):
inf = 99999
d = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
pred = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
visit= [ 0 if idx != s else 1 for idx in range(total_num_nodes) ]
q = deque([s])
return q,d, pred ,visit
def MLC_Deque(q,d, pred, visit, arcs):
while q != deque() :
i = q.popleft()
i_arcs = [ arc for arc in arcs if arc[0] == i]
for arc in i_arcs :
j = arc[1] ; cost = arc[2]
if d[j] > d[i] + cost :
d[j] = d[i] + cost
pred[j] = i
if j not in q :
if visit[j] == 0 :
q.append(j)
visit[j] = 1
else:
q.appendleft(j)
return d, pred