BFS可回答兩類問題：

1.從節點A出發，有前往節點B的路徑嗎？

2.從節點A出發，前往節點B的哪條路徑經過的節點最少？

BFS中會用到“隊列”的概念。隊列是一種先進先出（FIFO, first in first out）的數據結構，與棧不同，棧是后進先出（LIFO, last in first out）的數據結構。

還會用到“字典”的概念。字典在現在很多語言中都存在且廣泛使用，字典中的元素是一組<鍵（key），值（value）>對，key的值是不可以重復的。關于字典的詳細內容，網上有很多資料可以查閱。

問題描述：想從你的朋友中找出一個芒果銷售商，如果你的朋友中沒有，那么就從朋友的朋友中查找。（這里假設名字最后一個字母為“m”的即為芒果銷售商）。這樣就是從“you”這個節點出發，是否有到“Xm”這個節點的路徑的問題。

思路：先從你的朋友開始查找，如果朋友A是芒果銷售商，則程序結束，如果不是，則將A的朋友排到隊列中。然后檢查朋友B是否為芒果銷售商，循環，直到找到芒果銷售商或者隊列中的朋友們都被檢查了一遍。因為會有某個人C既是A的朋友又是B的朋友，而C只需要檢查一次，因此要分配一個列表用于記錄已經檢查過哪些朋友了。

Python代碼：

>>> from collections import deque>>> graph = {} >>> graph["you"]=["alice","bob","claire"] >>> graph["bob"] = ["anuj","peggy"] >>> graph["alice"] = ["peggy"] >>> graph["claire"]=["thom","jonny"] >>> graph["anuj"]=[] >>> graph["peggy"]=[] >>> graph["thom"]=[] >>> graph["jonny"]=[]>>> def search(name):search_queue = deque()search_queue += graph[name]searched = []while search_queue:person = search_queue.popleft()if person not in searched:if person_is_seller(person):print (person + " is a mango seller!")return Trueelse:search_queue += graph[person]searched.append(person)return False>>> def person_is_seller(name):return name[-1] == 'm'>>> search("you") thom is a mango seller! True

?C#代碼：

namespace Algorithms {public static class BFS{public static bool BreadthFirstSearch(string name, Dictionary<string,List<string>>graph){Queue<string> search_queue = new Queue<string>();foreach (var item in graph[name])search_queue.Enqueue(item);List<string> searched = new List<string>();while (search_queue.Count != 0){string person = search_queue.Dequeue();if (!searched.Contains(person)){if (JudgeSeller(person)){Console.WriteLine(person + " is a mango seller!");return true;}else{foreach (var item in graph[person])search_queue.Enqueue(item);searched.Add(person);}}}return false;}private static bool JudgeSeller(string name){if (name[name.Length - 1] == 'm')return true;return false;}} }

測試：

namespace Algorithms {class Program{static void Main(string[] args){Dictionary<string, List<string>> graph = new Dictionary<string, List<string>>();graph["you"] = new List<string>() { "alice", "bob", "claire" };graph["alice"] = new List<string>() { "peggy" };graph["bob"] = new List<string>() { "anuj", "peggy" };graph["claire"] = new List<string>() { "thom", "jonny" };graph["anuj"] = new List<string>();graph["peggy"] = new List<string>();graph["thom"] = new List<string>();graph["jonny"] = new List<string>();if (!BFS.BreadthFirstSearch("you", graph)){Console.WriteLine("no mango seller!");}Console.Read();}} }

?Dijkstra's algorithm 用于計算出最短路徑，但是這個算法在使用上有很多限制條件。

問題描述：從A地到B地的各種可能的路徑中，哪條路徑所用的時間最短。（圖中的數字表示從某地到另外某地所用的時間）

?

?

?

圖1

思路：記錄從A點到其他各個節點的所需的時間，如表1所示（現在還不知道從A到B的時間，則先設置為無窮大）

D	3
C	7
B	∞

?

表1

?

?

從所需時間最短的D點再出發，計算從A經過D到其他個各節點的時間，如表2所示

?

C	5
B	10

表2

?

?

直接前往C點需要的時間為7，而經過D點前往C點所需的時間為5，時間縮短了，則更新從A到各個點所需的時間的列表，如表3所示

?

D	3
C	5
B	10

?

表3

?

?

現在除了節點D之外，從A到C的時間是最短的了，則計算從A經過C再到其他節點的時間，如表4所示。

?

B

7

表4

?

現在從A經過D再經過C然后到B的時間為7，小于表3記錄的到B的時間，則更新這個時間。

就這樣得到了花費時間最短的路徑。總結一下就是，不斷的獲得從起點到某點的最短時間，然后更新這個時間列表。在?Dijkstra's algorithm中，這些數字被稱為“權重（weight）”，而帶權重的圖則被稱為加權圖（weighted graph），那么不帶權重的則被稱為非加權圖（unweighted graph）。對于計算非加權圖中的最短路徑，可使用BFS，計算加權圖中的最短路徑，可使用?Dijkstra's algorithm。然而，?Dijkstra's algorithm不適用于帶環的圖，即圖1中的箭頭如果是雙向的話那么就是不適用的。此外，它還不適用于帶有負權重的情況。

Dijkstra算法的實現需要使用三個散列表。第一個散列表記錄的是每個點的鄰居及權重。第二個散列表記錄的是從起點開始到每個節點的權重，第三個散列表記錄的是各個節點父節點。

Python代碼：

#第一個散列表，記錄每個點的鄰居及權重 graph={} graph["A"]={} graph["A"]["C"]=7 graph["A"]["D"]=3 graph["C"]={} graph["C"]["B"]=2 graph["D"]={} graph["D"]["C"]=2 graph["D"]["B"]=7 graph["B"]={}#第二個散列表，記錄從起點A到其他各個節點的權重 #由于節點B不是A的鄰居，則A到B的權重暫設置為無窮大 costs={} infinity = float("inf") costs["C"]=7 costs["D"]=3 costs["B"]=infinity#第三個散列表，用于存儲節點的父節點 parents={} parents["C"]="A" parents["D"]="A" parents["B"]=None#用于記錄已經處理過的節點的數組 processed=[]#先在未處理的節點數組中找到權重最小的節點 def find_lowest_cost_node(costs):lowest_cost = float("inf")lowest_cost_node = Nonefor node in costs:cost = costs[node]if cost < lowest_cost and node not in processed:lowest_cost = costlowest_cost_node = nodereturn lowest_cost_nodenode = find_lowest_cost_node(costs) while node is not None:cost = costs[node]neighbors=graph[node]for n in neighbors.keys():new_cost=cost + neighbors[n]if costs[n] > new_cost:costs[n] = new_costparents[n]=nodeprocessed.append(node)node=find_lowest_cost_node(costs)for node in costs:print("Node:" + node+ " Cost:" + str(costs[node]) + "\r\n")for node in parents:print("ChildNode:" + node + " ParentNode:" + parents[node] + "\r\n")

運行結果：

Node:C Cost:5Node:D Cost:3Node:B Cost:7ChildNode:C ParentNode:DChildNode:D ParentNode:AChildNode:B ParentNode:C>>>

C#代碼：

public class DijkstraAlgorithm{public Dictionary<string, double> Costs { get; set; }public Dictionary<string, string> Parents { get; set; }public Dictionary<string, Dictionary<string,double>> Graph { get; set; }private List<string> processed = new List<string>();public DijkstraAlgorithm(){Costs = new Dictionary<string, double>();Parents = new Dictionary<string, string>();Graph = new Dictionary<string, Dictionary<string, double>>();}public void Dijkstra_Algorithm(){string node = FindLowestCostNode();while(node != null){double cost = Costs[node];Dictionary<string, double> neighbors = Graph[node];foreach(KeyValuePair<string,double> item in neighbors){double new_cost = cost + item.Value;if (Costs[item.Key] > new_cost){Costs[item.Key] = new_cost;Parents[item.Key] = node;}}processed.Add(node);node = FindLowestCostNode();}}private string FindLowestCostNode(){string lowestcostnode = null;double lowestcost = double.PositiveInfinity;foreach(KeyValuePair<string,double> item in Costs){if(item.Value < lowestcost && !processed.Contains(item.Key)){lowestcost = item.Value;lowestcostnode = item.Key;}}return lowestcostnode;}}

字典的初始化以及運行結果：

DijkstraAlgorithm Dalgorithm = new DijkstraAlgorithm();Dalgorithm.Graph["A"] = new Dictionary<string, double>();Dalgorithm.Graph["A"]["C"] = 7;Dalgorithm.Graph["A"]["D"] = 3;Dalgorithm.Graph["C"] = new Dictionary<string, double>();Dalgorithm.Graph["C"]["B"] = 2;Dalgorithm.Graph["D"] = new Dictionary<string, double>();Dalgorithm.Graph["D"]["C"] = 2;Dalgorithm.Graph["D"]["B"] = 7;Dalgorithm.Graph["B"] = new Dictionary<string, double>();Dalgorithm.Costs["C"] = 7;Dalgorithm.Costs["D"] = 3;Dalgorithm.Costs["B"] = double.PositiveInfinity;Dalgorithm.Parents["C"] = "A";Dalgorithm.Parents["D"] = "A";Dalgorithm.Parents["B"] = null;Dalgorithm.Dijkstra_Algorithm();foreach(KeyValuePair<string,double> item in Dalgorithm.Costs){Console.WriteLine("Key : " + item.Key + " Value : " + item.Value);}foreach(KeyValuePair<string,string> item in Dalgorithm.Parents)Console.WriteLine("Key : " + item.Key + " Value : " + item.Value);Console.Read();

轉載于:https://www.cnblogs.com/larissa-0464/p/10633934.html

總結

以上是生活随笔為你收集整理的广度优先搜索（BreadthFirstSearch） 迪克斯特拉算法 （Dijkstra's algorithm）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。