<jupyter_start><jupyter_text>Week2 code1 Dijkstra's shortest-path algorithmThe algorithm is designed for computing shortest path from one specific vertex to other vertices among a non-negative directed acyclic graph. The BFS also can be used for computing shortest path, but it has an assumption that all length of edges should be one.More advanced implementation involved using a customized heap data structure, which is not involved in this submission.<jupyter_code>class Dijkstra(Model):
    def __init__(self):
        super().__init__()

        
    def preprocess(self):
        # No need preprocessing for this algorithm
        self.data = self.dataLoader.data
        self.codedict = {}
    
        
    def model(self):
        source_vertex = 1

        # Initialize data structure
        number_of_vertices = max([i[0] for i in m.data])  #index start from 1

        # Initialize processed set
        X = set([source_vertex])

        # Initialzie all vertices set
        V = set(range(1,number_of_vertices+1))

        # Initialize shorest distance list, index is vertex, value is shortest distance
        A = [0 for _ in range(0,number_of_vertices+1)]
        
        # Initialize PATH list, which is only for explanation
        B = [str(source_vertex) for _ in range(0,number_of_vertices+1)]

        # Main loop
        while X != V:

            scorelist = []
            # filter out all edge that head is in X but tail is not
            for i in m.data:
                if i[0] in X:
                    for edge in i[1:]:
                        if edge[0] not in X:
                            scorelist.append([i[0],edge[0], A[i[0]] + edge[1]])

            # compute the shortest one
            selected_edge = min(scorelist,key = lambda x:x[2])

            # updating new vertex 
            old_vertex = selected_edge[0]
            nex_vertex = selected_edge[1]

            #updating A,B
            A[nex_vertex] = selected_edge[2]
            B[nex_vertex] = B[old_vertex] + ('->' + str(selected_edge[1]))
            X.add(nex_vertex)

#             print("Adding ", nex_vertex," to the set X, distance:" , selected_edge[2] )
        
        for i in range(len(A[1:])):
            print("Vertex:",A[1:][i],", PATH:", B[1:][i])
        
        # this is the part for the quiz submission
        temp = [A[i]  for i in range(201) if i in [7,37,59,82,99,115,133,165,188,197]] 
        result = ""
        for i in temp:
            result += ',' + str(i)
        return result[1:]
processLine = lambda x : [int(i) if i.isdigit() else [int(j) for j in i.split(",")] for i in map(str.strip,x.split())]
arg = {'fileName':'./data/dijkstraData.txt','numLines':None ,  'processLine' : processLine  }

d = DataLoader(**arg)
m = Dijkstra()
s = Setting(d,m,False)
s.run()<jupyter_output>Loading data ...
Total 200 lines read
--------------------------------------------------
Vertex: 0 , PATH: 1
Vertex: 2971 , PATH: 1->114->129->85->53->34->2
Vertex: 2644 , PATH: 1->80->119->195->144->3
Vertex: 3056 , PATH: 1->49->4
Vertex: 2525 , PATH: 1->92->134->158->181->51->5
Vertex: 2818 , PATH: 1->92->128->123->6
Vertex: 2599 , PATH: 1->114->129->85->53->7
Vertex: 1875 , PATH: 1->80->119->130->8
Vertex: 745 , PATH: 1->92->70->9
Vertex: 3205 , PATH: 1->92->70->9->72->96->10
Vertex: 1551 , PATH: 1->92->134->11
Vertex: 2906 , PATH: 1->80->119->154->200->67->12
Vertex: 2394 , PATH: 1->92->134->135->13
Vertex: 1803 , PATH: 1->92->70->9->131->14
Vertex: 2942 , PATH: 1->80->119->87->159->61->163->15
Vertex: 1837 , PATH: 1->114->35->16
Vertex: 3111 , PATH: 1->145->108->17
Vertex: 2284 , PATH: 1->80->119->154->18
Vertex: 1044 , PATH: 1->80->19
Vertex: 2351 , PATH: 1->92->20
Vertex: 3630 , PATH: 1->92->128->123->46->193->21
Vertex: 4028 , PATH: 1->145->108->143->25->132->22
Vertex: 2650 , [...]
{'fraction_non_alphanumeric': 0.16183006535947714, 'fraction_numerical': 0.09908496732026144, 'mean_word_length': 2.338568935427574, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 97, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '98450', 'license': 'MIT', 'n_tokens_mistral': 1511, 'n_tokens_neox': 1234, 'n_words': 362, 'path': 'course2/.ipynb_checkpoints/Week2Code-checkpoint.ipynb', 'repo_name': 'Cuilie/Code-for-algorithm-stanford-coursera', 'size': '3825'}