## Dijkstra

介紹Dijkstra的演算法，這是一種用來尋找圖中兩點之間最短路徑的演算法。主要內容：

- Dijkstra /ˈdɛɪkstra/.
- 權重（Weights）：圖的邊可以帶有權重，這代表從一個節點到另一個節點的「成本」。例如在地圖中，權重可能代表兩地點之間的距離長度或者所需的時間。
- 有向圖和無向圖：圖的邊可以是有向的或者無向的。
- Dijkstra演算法適用於有向圖。但不適用循環圖
- Dijkstra演算法 : 給定一個起點與終點，計算出從該點到圖中所有其他點的最短路徑。
- 首先將最短路徑設定為無窮大
- 不斷進行更新鄰居節點，直到造訪所有節點並碰到終點。
- 過程中，演算法會使用一個叫做「優先佇列」的資料結構。

- *優先佇列可以用不同的實現方式來實現，例如二叉堆（Binary Heap）、斐波那契堆（Fibonacci Heap）或平衡二叉搜索樹（Balanced Binary Search Tree）等。不同的實現方式具有不同的時間和空間複雜度特性。
- 負權重：如果圖的邊存在負權重，則不能使用Dijkstra的演算法。可以使用另一種叫做Bellman-Ford的演算法。

## Weight



## Working with Dijkstra


初始化，你需要建立一個記錄起點到圖中每個節點距離的表格。這個距離在開始時會被初始化為無窮大（除了起點到自己的距離為0）。你還需要一個儲存已處理節點的清單。
- 權重花費最少的節點：找出起點可以直接到達的最便宜的節點。
- 鄰居節點的開銷：對於該節點的每一個鄰居，你需要計算如果經過該節點到達鄰居節點的開銷，如果該開銷比現有記錄的開銷小，則更新該鄰居節點的開銷。
- 重複第2步和第3步：直到所有節點都被處理，加入到已處理節點的清單中。
- 最終路徑：最後表格中記錄的就是從起點到圖中每個節點的最短路徑。

## Three hash table

## 第一步
- 設立起點和終點
- A需要6分，B需要2分


## 第二步
- 往B，計算B前往其他節點所需時間
- B to A = 3, B to End = 5
- 起點 to A更新為2+3, 終點為2+5

## 重複
- 更新A節點開銷
- A to End = 1
- 起點 B A End = 6
- 起點 B End = 7



## Weight & Cycle


## 換鋼琴

## 負權重

## 時間複雜度

- 使用無優先級隊列（Unsorted Priority Queue）：在這種實現方式下，Dijkstra算法的時間複雜度為O((V + E) * log(V))，其中V是節點的數量，E是邊的數量。這是因為每個節點最多需要進行一次插入和刪除操作，而這些操作的時間複雜度是log(V)。對於每條邊，我們需要檢查和更新相關節點的最短距離。
- 使用二叉堆（Binary Heap）：在這種實現方式下，Dijkstra算法的時間複雜度為O((V + E) * log(V))。二叉堆的插入和刪除操作的時間複雜度是log(V)，因此整體時間複雜度與無優先級隊列相同。然而，使用二叉堆在實現上更複雜，但它在實際中可以提供更好的性能。
- 使用斐波那契堆（Fibonacci Heap）：在這種實現方式下，Dijkstra算法的時間複雜度為O(V * log(V) + E)，其中V是節點的數量，E是邊的數量。斐波那契堆的插入和刪除操作的平攤時間複雜度是常數，而不是log(V)，這使得整體時間複雜度更優秀。然而，斐波那契堆在實現上更複雜且較為複雜，因此在實際中並不常見。
- Dijkstra算法的時間複雜度與節點和邊的數量成正比，並且與使用的結構有關。在實際應用中，根據具體的問題規模和性能需求，選擇合適的實現方式可以確保算法的效率。

## Ruby Implementation

def dijkstra(graph, source)
  # Step 1: Initialize distance hash and processed nodes array
  distances = {}
  processed = []

  graph.keys.each do |node|
    distances[node] = Float::INFINITY
  end
  distances[source] = 0

  # Step 2: While there are nodes left to process
  while processed.length != graph.keys.length
    # Find the node with the smallest weight
    unprocessed = distances.select { |node, weight| !processed.include? node }
    puts "unprocessed=>#{unprocessed}"
    closest = unprocessed.min_by { |node, weight| weight }
    puts "closest=>#{closest}"
    # Break the loop if there is no more reachable node
    break if closest[1] == Float::INFINITY

    node = closest[0]
    puts "node=>#{node}"

    # Step 3: Update distances to neighboring nodes
    graph[node].each do |neighbour, value|
      puts "#{neighbour},#{value},#{distances[node]}"
      new_distance = distances[node] + value
      distances[neighbour] = new_distance if new_distance < distances[neighbour]
    end
    puts "distances=>#{distances}"

    # Mark the current node as processed
    processed << node
  end

  distances
end

# Example usage:

graph = {
  "start" => { "A" => 6, "B" => 2 },
  "A" => { "finish" => 1 },
  "B" => { "A" => 3, "finish" => 5 },
  "finish" => {}
}

puts dijkstra(graph, "start")

# => {"start"=>0, "A"=>5, "B"=>2, "finish"=>6}

## Bellman-ford

- 能夠檢測並處理帶有負權重的圖。
- 檢查是否存在負權重：再執行一次所有邊的操作。如果在這一輪操作中，任何節點的最短路徑長度仍然能夠進一步改善，則繼續執行執行。
- 演算法的時間複雜度為 O(V * E)，其中 V 是節點的數量，E 是邊的數量。由於其較高的時間複雜度，當圖的規模很大時，改使用其他更高效的最短路徑算法（如Dijkstra算法）。