最短路徑
含有「最短路徑」共 12 篇內容
全部內容
發佈日期由新至舊
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。
我們專注於廣度優先搜尋(BFS)演算法，以等權圖的最短路徑為例，
詳細說明如何利用BFS從起點擴散到終點，並且提供詳細的程式碼範例。
透過實作，讀者能夠更清楚理解圖論及BFS的應用，並體會水波紋擴散模型的重要性。
付費限定
Path with Maximum Probability
題目給定一個無向圖(雙向移動皆可)，
提供每條邊的起終點，和每條邊對應的通過時的成功機率。
請問從起點start走到終點end的最高成功機率是多少?
如果完全沒有路徑可以抵達，則返回0。
😆這樣開可以嗎？
付費限定
題目敘述: Minimum Cost to Convert String I
給定字元轉換映射表original, changes和對硬的成本陣列cost。
請問字串source轉換到字串destination的最小成本是多少?
如果無解，請返回-1
如果有解，請返回整體的轉換最小成本。
冰冰表示：我要來支持一下天書，雖然我看不懂🤣
付費限定
這篇文章，會帶著大家複習以前學過的BFS框架，
並且以圖論的應用題與概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
BFS 框架 + 演算法 虛擬碼
# Queue 通常初始化成根結點，作為起點
BFS_queue = deque([root])
# 先
上篇進一步認識基本的圖形架構與三大 Graph 算法，那首先從 shortest path 開始，我們會陸續去理解這些算法，以及可能的應用，如果還沒有看過上一篇的，可以點以下連結～那我們就開始吧！
【圖論Graph】Part1：初探圖形與圖形演算法之應用
付費限定
題目敘述
題目會給定一個二維陣列grid，代表每顆橘子分布的位置和初始狀態。
0: 這個格子點沒有東西。
1: 這個格子點有一顆新鮮的橘子。
2: 這個格子點有一顆壞掉的橘子。
壞掉的橘子上面的黴菌，
每隔一個週期，可以向上、下、左、右 N4四連通的格子點感染一次。
請問，最少需要多
老師請問為什麼一定要time_stamp, 不是我每次做完把time_record加一就好了嗎
題目敘述
題目會給我們一個4位數字的數字鎖，還有解鎖的密碼target，和陷阱數字deadends(假如遇到的會鎖會直接卡住，不能在撥動轉盤了)。
預設開始的狀態是0000，請問，最少要撥動轉盤幾次才能解鎖?
題目的原文敘述
測試範例
Example 1:
Input: deaden
付費限定
題目敘述
題目給定一個二維陣列maze代表迷宮的布局，
其中標記為"."的地方代表可通過，標記為"+"代表牆壁不可通過。
每次移動的時候，可以選擇往上、下、左、右移動一格。
請問從出發點entrace開始走的話，抵達迷宮出口最短距離的步數是多少？
如果無解的話，返回-1。
題目的原文敘述
題目敘述
題目會給我們一個輸入陣列arr，起始點固定在索引為0的位置，
終點固定在索引為n-1的位置。
假設當下所在的索引位置為i，那麼每次移動的時候，可以跳到i-1，i+1，或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。
例如:
假設當下在i=3
題目會給我們一個routes 陣列，裡面都是分別代表每一條公車路線所對應的公車站編號。
題目要求我們計算出，從起點站source到終點站target的最精簡公車路線搭乘次數是幾次?
也就是說，就是在最少轉乘的前提下，旅途中需要搭乘幾條公車路線?
