다익스트라 Dijkstra 파이썬 python 구현

다익스트라란?

다이나믹 프로그래밍을 활용해 최단거리를 찾는 알고리즘. 특정 source 노드에서 다른 점으로 가는 최단 경로를 알려준다.

다익스트라가 다이나믹 프로그래밍인 이유:

이전에 구했던 최단거리를 이용해서 다음 최단거리를 계산하기 때문

 

다익스트라 문제 : 최단 경로 문제

최단 경로 문제란?

두 노드를 잇는 가장 짧은 경로를 찾는 문제

그래프 간선 사이 비용이 있을 떄에 간선의 비용 합이 최소가 되는 경로를 찾는 문제

 

 

다익스트라 작동 순서:

다익스트라 알고리즘은 프라임의 Minimum Spanninng Tree 알고리즘과 매우 비슷합니다.  

자세한 설명은 나동빈님 블로그 참조하세요. blog.naver.com/ndb796/221234424646

 

 

파이썬 코드:

import sys # Library for INT_MAX 
 	  
class Graph(): 
  
    def __init__(self, vertices): 
        self.V = vertices 
        self.graph = [[0 for column in range(vertices)]  
                    for row in range(vertices)] 
  
    def printMST(self, parent): 
        print "Edge \tWeight"
        for i in range(1, self.V): 
            print parent[i], "-", i, "\t", self.graph[i][ parent[i] ] 
    def minKey(self, key, mstSet): 
  
        # Initilaize min value 
        min = sys.maxint 
  
        for v in range(self.V): 
            if key[v] < min and mstSet[v] == False: 
                min = key[v] 
                min_index = v 
  
        return min_index 
  
    def primMST(self): 
  
        key = [sys.maxint] * self.V 
        parent = [None] * self.V # Array to store constructed MST 
        key[0] = 0 
        mstSet = [False] * self.V 
  
        parent[0] = -1 # First node is always the root of 
  
        for cout in range(self.V): 
  
            u = self.minKey(key, mstSet) 
  
            mstSet[u] = True
  
            for v in range(self.V): 
  
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]: 
                        key[v] = self.graph[u][v] 
                        parent[v] = u 
  
        self.printMST(parent) 
  
g = Graph(5) 
g.graph = [ [0, 2, 0, 6, 0], 
            [2, 0, 3, 8, 5], 
            [0, 3, 0, 0, 7], 
            [6, 8, 0, 0, 9], 
            [0, 5, 7, 9, 0]] 
  
g.primMST(); 
  
# Contributed by Divyanshu Mehta 

참조: www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/