1 files changed, 85 insertions, 0 deletions
diff --git a/082.py b/082.py
new file mode 100644
index 0000000..b0fd92a
--- /dev/null
+++ b/082.py
@@ -0,0 +1,85 @@
+
+# uses Dijkstra's algorithm to find minimal path
+# (based on solution for problem 81)
+#
+# slow, but working
+
+infinity = 99999999
+
+matrix = []
+
+width = 80
+height = 80
+
+f = open('082.txt', 'r')
+for line in f:
+	line.rstrip('\n')
+	line_str = line.split(',')
+	line_int = [ int(x) for x in line_str ]
+	matrix.append(line_int)
+f.close()
+
+globalmin = 500000
+
+for currentrow in range(height):
+
+	# initialize
+	distance = [infinity] * (width*height)
+	pre = [None] * (width*height)
+	distance[currentrow*width] = 0  # start node
+	Q = range(width*height)
+
+	def mindistance(Q):
+		mini = Q[0]
+		mind = distance[mini]
+		for i in Q:
+			if distance[i] < mind:
+				mind = distance[i]
+				mini = i
+		return mini
+
+	def neighbors(u):
+		n = []
+		row = u / width
+		col = u % width
+		if col == 0:
+			return[u+1]
+		if col < width-1:
+			n.append(row*width + col + 1) # right neighbor
+		if row < height-1:
+			n.append((row+1)*width + col) # lower neighbor
+		if row > 0:
+			n.append((row-1)*width + col) # upper neighbor
+		return n
+
+	def update(u, v):
+		alt = distance[u] + matrix[v/width][v%width]
+		if alt < distance[v]:
+			distance[v] = alt
+			pre[v] = u
+
+	# main algorithm
+	while len(Q) > 0:
+		u = mindistance(Q)
+		Q.remove(u)
+		for v in neighbors(u):
+			if v in Q:
+				update(u, v)
+
+	# search min distance
+	for targetrow in range(height):
+		u = targetrow*width-1  # target node
+		path = [ u ]
+		while pre[u] != None:
+			u = pre[u]
+			path = [u] + path
+
+		minsum = 0
+		for n in path:
+			minsum += matrix[n/width][n%width]
+
+		if minsum < globalmin:
+			globalmin = minsum
+
+print globalmin
+