Best-first Search
Best-first search (BFS) algorithms process a graph using the most promising nodes first according to specified selection rules, such as the cost of processing.
BFS finds the shortest path on an unweighted graph because it explores the path with the fewest steps before paths with more steps.
Examples of specific best-first search algorithms include:
Greedy BFS Example
In the Greedy BFS example illustrated below, a best path in Romania from Arad to Bucharest is calculated,
Best-first Search Dijkstra Pseudo Code Example
More information on this algorithm can be found here.
function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph:
6 dist[v] ← INFINITY
7 prev[v] ← UNDEFINED
8 add v to Q
10 dist[source] ← 0
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u]
14
15 remove u from Q
16
17 for each neighbor v of u:
18 alt ← dist[u] + length(u, v)
19 if alt < dist[v]:
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]