• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jan 23rd, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Graph:
2.     def __init__(self):
3.         self.graph = {
4.            'A': {'B': 10, 'D': 4, 'F': 10},
5.            'B': {'E': 5, 'J': 10, 'I': 17},
6.            'C': {'A': 4, 'D': 10, 'E': 16},
7.            'D': {'F': 12, 'G': 21},
8.            'E': {'G': 4},
9.            'F': {'H': 3},
10.            'G': {'J': 3},
11.            'H': {'G': 3, 'J':5},
12.            'I': {},
13.            'J': {'I': 8}
14.         }
15.
16.     def shortpath(self, start, end):
17.         D = {}
18.         P = {}
19.
20.          for knote in self.graph.keys():
21.             D[knote] = - 1
22.             P[knote] = ""
23.
24.         D[start] = 0
25.
26.
27.         unvisited_n = list(self.graph.keys())
28.
29.         while len(unvisited_n) > 0:
30.
31.             shortest = None
32.             knote = ''
33.             for temp_node in unvisited_n:
34.                 if shortest == None:
35.                     shortest = D[temp_node]
36.                     node = temp_node
37.                 elif D[temp_node] < shortest:
38.                     shortest = D[temp_node]
39.                     knote = temp_node
40.
41.                 if knote in unvisited_n:
42.                     unvisited_n.remove(knote)
43.
44.
45.         for c_knote, v_value in self.graph[knote].items():
46.             if D[c_knote] < D[knote] + v_value:
47.                 D[c_knote] = D[knote] + v_value
48.
49.                 P[c_knote] = knote
50.
51.                 path = []
52.
53.                 knote = end
54.
55.
56.         while not (knote == start):
57.             if path.count(knote) == 0:
58.                 path.insert(0, knote)
59.                 knote = P[knote]
60.             else:
61.                 break
62.                 path.insert(0, start)
63.             return path
64.
65. def main():
66.     gg = Graph()
67.     path = gg.shortpath('C', 'I')
68.     print(path)
69.
70. if __name__ == '__main__':
71.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top