# Lab3: Dijsktra's Algorithm

## 實驗場景

* 輸入網路拓樸資料及起始點
* 輸出shortest-path tree，其cost需為最小。

上圖的例子中，起始點為u。

## 拓樸檔案


[拓樸檔案下載](https://drive.google.com/file/d/1zclLnHWpUwYR3yUUTstOcB4H5Se3VEhO/view?usp=sharing)

在拓樸檔案之中，第一行表示這個網路拓樸中的node數。node的index為0~ (node數-1)。例如node為6，則node的index為0~5如上圖例。第二行之後為link的資訊。第一個和第二個column為link兩端node的index，而第三個column為這個link的cost。link為雙向的，且兩個方向的cost相同。例如node 3可以傳東西到node 5，則node 5也可以傳東西到node 3。

## 拓樸類別

以下類別在產生物件時會去讀入拓樸檔案，並將拓樸資訊存入物件之中。

import numpy as np

class Topo:

    def __init__(self, filename):
        self.filename = filename
        f = open(self.filename, 'r')
        i = 0

        for line in f.readlines():
            if i == 0:
                self.numNodes = int(line)
                i = 1
                self.links = np.zeros((self.numNodes, self.numNodes))
            else:
                tokens = line.split()
                self.links[int(tokens[0])][int(tokens[1])] = int(tokens[2])
                self.links[int(tokens[1])][int(tokens[0])] = int(tokens[2])

    def printLinks(self):
        for i in range(self.numNodes):
            for j in range(self.numNodes):
                if self.links[i][j] > 0:
                    print(i, '-->', j, '\t', self.links[i][j])

[拓樸類別檔案下載](https://drive.google.com/file/d/1eaS_KF4AWSCCULNU6YUfDDKyTe2_RYJQ/view?usp=sharing)

* numNodes: the number of nodes in the topology
* links\[\<A>\]\[\<B>\]: if larger than 0, there is a link from node \<A> to node \<B>
* EX: links\[2\]\[3\] = 5: the cost of link from node 2 to node 3 is 5
* links\[\<A>\]\[\<B>\] is equal to links\[\<B>\]\[\<A>\]

## Shortest-path tree的計算

請完成下面的程式來計算shortest-path tree

from topo import Topo
import numpy as np

start = 0

myTopo = Topo('input.txt')

N = np.zeros((myTopo.numNodes, 1))
D = np.zeros((myTopo.numNodes, 1))
p = np.zeros((myTopo.numNodes, 1))

for i in range(myTopo.numNodes):
    D[i] = -1
    p[i] = -1
    N[i] = -1

N[0] = start
D[start] = 0
p[start] = start

# TODO: your codes here

for i in range(1, myTopo.numNodes):
    print(int(p[i]), ' --> ', i, ' cost = ', int(D[i]))

[程式碼下載](https://drive.google.com/file/d/1zxyqsIjSOMWNiJgP8n3hdyMEGSd8qdxN/view?usp=sharing)

* D\[\]: current value of cost of path from source to dest. v
* p\[\]: predecessor node along path from source to v
* N\[\]: set of nodes whose least cost path definitively known