Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Blog
aaa
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
""" Uniform Cost Search Implementation using PriorityQueue Map and input taken from http://www.massey.ac.nz/~mjjohnso/notes/59302/l04.html Author: Jayesh Chandrapal Version: 1.0 """ import queue as Q def search(graph, start, end): if start not in graph: raise TypeError(str(start) + ' not found in graph !') return if end not in graph: raise TypeError(str(end) + ' not found in graph !') return queue = Q.PriorityQueue() queue.put((0, [start])) while not queue.empty(): node = queue.get() current = node[1][len(node[1]) - 1] if end in node[1]: print("Path found: " + str(node[1]) + ", Cost = " + str(node[0])) break cost = node[0] for neighbor in graph[current]: temp = node[1][:] temp.append(neighbor) queue.put((cost + graph[current][neighbor], temp)) def readGraph(): lines = int( input() ) graph = {} for line in range(lines): line = input() tokens = line.split() node = tokens[0] graph[node] = {} for i in range(1, len(tokens) - 1, 2): # print(node, tokens[i], tokens[i + 1]) # graph.addEdge(node, tokens[i], int(tokens[i + 1])) graph[node][tokens[i]] = int(tokens[i + 1]) return graph def main(): graph = readGraph() search(graph, 'Arad', 'Bucharest') if __name__ == "__main__": main() """ Sample Map Input: 14 Arad Zerind 75 Timisoara 118 Sibiu 140 Zerind Oradea 71 Arad 75 Timisoara Arad 118 Lugoj 111 Sibiu Arad 140 Oradea 151 Fagaras 99 RimnicuVilcea 80 Oradea Zerind 71 Sibiu 151 Lugoj Timisoara 111 Mehadia 70 RimnicuVilcea Sibiu 80 Pitesti 97 Craiova 146 Mehadia Lugoj 70 Dobreta 75 Craiova Dobreta 120 RimnicuVilcea 146 Pitesti 138 Pitesti RimnicuVilcea 97 Craiova 138 Bucharest 101 Fagaras Sibiu 99 Bucharest 211 Dobreta Mehadia 75 Craiova 120 Bucharest Fagaras 211 Pitesti 101 Giurgiu 90 Giurgiu Bucharest 90 """
14 Arad Zerind 75 Timisoara 118 Sibiu 140 Zerind Oradea 71 Arad 75 Timisoara Arad 118 Lugoj 111 Sibiu Arad 140 Oradea 151 Fagaras 99 RimnicuVilcea 80 Oradea Zerind 71 Sibiu 151 Lugoj Timisoara 111 Mehadia 70 RimnicuVilcea Sibiu 80 Pitesti 97 Craiova 146 Mehadia Lugoj 70 Dobreta 75 Craiova Dobreta 120 RimnicuVilcea 146 Pitesti 138 Pitesti RimnicuVilcea 97 Craiova 138 Bucharest 101 Fagaras Sibiu 99 Bucharest 211 Dobreta Mehadia 75 Craiova 120 Bucharest Fagaras 211 Pitesti 101 Giurgiu 90 Giurgiu Bucharest 90
[
-
]
Show input
Absolute running time: 0.14 sec, cpu time: 0.03 sec, memory peak: 6 Mb, absolute service time: 0,14 sec
edit mode
|
history
|
discussion
Path found: ['Arad', 'Sibiu', 'RimnicuVilcea', 'Pitesti', 'Bucharest'], Cost = 418