Dijkstra algorithm

dijkstra-functional-way.py

graph = [[0, 7, 9, -1, -1, 14], [7, 0, 10, 15, -1, -1], [9, 10, 0, 11, -1, 2], [-1, 15, 11, 0, 6, -1], [-1, -1, -1, 6, 0, 9], [14, -1, 2, -1, 9, 0]]
start = 3


def dijkstra(graph, start):
  r = range(len(graph))

  def perform(results, work_results, visited, path, current):
    tested = set(filter(lambda i: (graph[current][i] >= 0) and not visited[i] and ((results[current] + graph[current][i]) < results[i]), r))

    results = map(lambda i: results[current] + graph[current][i] if i in tested else results[i], r)
    path = map(lambda i: path[current] + [i] if i in tested else path[i], r)
    work_results = map(lambda i: results[current] + graph[current][i] if i in tested else work_results[i], r)

    work_results[current] = float("inf")
    visited[current] = True

    if all(visited):
      return [results, path]
    else:
      return perform(results, work_results, visited, path, work_results.index(min(work_results)))

  return perform(
          map(lambda i: float("inf") if i != start else 0, r),
          map(lambda i: float("inf") if i != start else 0, r),
          map(lambda i: False, r),
          map(lambda i: [start], r),
          start
        )

print dijkstra(graph, start)

dijkstra.py

graph = [[0, 7, 9, -1, -1, 14], [7, 0, 10, 15, -1, -1], [9, 10, 0, 11, -1, 2], [-1, 15, 11, 0, 6, -1], [-1, -1, -1, 6, 0, 9], [14, -1, 2, -1, 9, 0]]
start = 3

range = xrange(0, len(graph[0]), 1)

results = []
work_results = []
visited = []
path = []
for i in range:
  results.append(float("inf"))
  work_results.append(float("inf"))
  visited.append(False)
  path.append([start])

results[start] = 0
work_results[start] = 0

all_visited = False

while not all_visited:
  print "\nNew step"
  current = work_results.index(min(work_results))
  
  for i in range:
    if (graph[current][i] >= 0) and not visited[i] and ((results[current] + graph[current][i]) < results[i]):
      results[i] = results[current] + graph[current][i]
      path[i] = path[current] + [i]
      work_results[i] = results[current] + graph[current][i]
  
  work_results[current] = float("inf")
  visited[current] = True
  check = True
  for point in visited:
    check = check and point
  all_visited = check
  current = False
  
  print results
  print path
  print visited

print "\n----\nThe end"
print results
print path