最短路徑問題的原理及畫法-tft每日頭條

最短路徑問題的原理及畫法

生活更新时间:2024-09-02 14:18:15

最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：

确定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。适合使用Dijkstra算法。
确定終點的最短路徑問題 - 與确定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與确定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的确定起點的問題。
确定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題 - 求圖中所有的最短路徑。适合使用Floyd-Warshall算法。

用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：

Dijkstra算法
A*算法
Bellman-Ford算法
SPFA算法（Bellman-Ford算法的改進版本）
Floyd-Warshall算法
Johnson算法
Bi-Direction BFS算法

帶約束條件的最短路問題

以上說明的是基本最短路問題，這裡要介紹的是帶有約束條件的最短路問題，例如：

最多走10步
有必須要經過的點、邊
有不能經過的點、邊

解決方法其實隻需要一個思路：拆點構圖，即點附狀态。約束條件有幾種可能的組合方式，就有幾種狀态。例如，最多走5步，有兩個必須經過的點，有兩個必須經過的邊，（先不考慮不能經過），那麼狀态數就是，6*3*3=54，即每個點有54種狀态。

以Dijkstra為例

先來複習下Dijkstra算法，其僞代碼如下：

最短路徑問題的原理及畫法（帶約束條件的最短路問題）1

考慮上述拆點構圖我們需要做什麼呢？首先在描述距離的數組d要增加維度，例如d[n][54]。這樣，我們的以确定最優路徑集合S，未确定最優集合Q，就不能再是單純的點集，而應該是(點狀态)集。其次在11到14行，以确定最優點優化其他點是，應當根據約束條件計算出被優化點的狀态是什麼，再去更新該狀态的點。同樣previous數組也應記錄的是，s1狀态點p1的前一點是s0狀态的點p0。

最後，考慮不能經過的點、邊，估計你早有思路，就是把該點、邊從你的圖結構中直接抹去。

OK，到此為止，闡述完畢。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部

网友关注

生活張譯得影帝的是哪部劇
張譯是大家都很熟悉的一個實力派的演員。小的時候張譯夢想當一名播音員，但在第一次高考時落榜，第二次高考他堅決還是要報考北京廣播學院，不過還是沒有考上，正好趕上哈爾濱話劇學院招表演學習班，張譯也順利的進入了話劇班，慢慢的他就喜歡上了話劇，并在2... 2023-03-06
生活人血白蛋白屬于大病報銷嗎
導讀據湖州市中心血站信息，6月26日起，無償獻血者及其家屬的臨床用血費用，隻需幾分鐘就可以在辦理出院結算時一并減免。“沒想到簽一個減免書就把用血費減掉了，不用再去辦報銷手續真是方便了不少！”7月1日上午，在湖州長興縣人民醫院住院部出院用血報... 2023-03-26
生活 12年捷達前保險杠拆卸
12年捷達前保險杠拆卸?大衆新捷達保險杠拆卸先把前保險杠車底下部位的螺絲拆下來再打開前蓋，打開前蓋了不能急着拆螺絲，得先看看前燈的安裝螺絲，一般車輛是要拆二顆大燈螺絲，在大燈下面還有三顆螺絲将保險杠固定在車的龍骨上，現在小編就來說說關于12... 2022-06-01
生活南京江甯鄉村遊
古韻洪藍四季果飄香，農事體驗活動不斷。近年來，溧水區洪藍街道高質量成功打造一二三三産融合發展先導區，“賞梅花，采草莓，吃農家菜，逛遇園”已成為溧水及南京周邊家喻戶曉的精品旅遊線路。年底啦，不妨找個周末，帶上孩子來溧水的鄉村撒個野。近日，位于... 2023-02-02
生活衛生間有異味教你三招輕松搞定
#電熱毛巾架#家是我們每個人都需要的，不管你的是大房子還是臨時租的，反正都是過日子的，很多人都會遇到一種問題吧！衛生間用久了會有異味跟潮濕，味道難消除，真的是太麻煩了而且各種方法都嘗試了還沒效果吧？奧享電熱毛巾架其實我也是過來人，後來發現這... 2023-03-07
生活拍身份證黃頭發怎麼辦
拍身份證黃頭發怎麼辦?黃頭發是不可以拍身份證照片的，可以理掉再拍，我來為大家科普一下關于拍身份證黃頭發怎麼辦?下面希望有你要的答案，我們一起來看看吧!拍身份證黃頭發怎麼辦黃頭發是不可以拍身份證照片的，可以理掉再拍。根據公安部規定，身份證照相... 2022-06-08
生活怎麼選擇适合自己的眼鏡框架
想要配出的眼鏡新潮有個性，鏡架的款式一定要選好，好看的眼鏡框給我們的外貌增加氣場。市場上的眼鏡類型豐富多彩，各有特色，選擇起來真的要廢一些心思。為方便消費者快速選準自己喜歡的眼鏡類型，特做了眼鏡架的分類及這些系列的眼鏡架特點，接下來，我們一... 2023-02-14
生活歌詞萬物生而平凡
原創｜王陳羚亦我鹹蘿蔔吃多了呗。//@血色蘭陵：真操心！摘自：我的文章《簡析歌詞，閑談歌詞是如何從詩變成扯淡的過程》評論區——我和一位讀者的對話。前言3月5号晚上，在今日頭條上發布了一篇對歌曲《萬物生》歌詞簡析的文章。兩天時間有數萬閱讀量和... 2023-02-20
生活塞爾維亞國旗和俄羅斯國旗一樣
【塞爾維亞将國旗與五星紅旗系在一起】當地時間3月21日，中國6人專家醫療隊抵達塞爾維亞，随着專機帶來的有中國政府緊急籌集的十幾噸物資，塞爾維亞總統武契奇等多位政府官員在停機坪迎接。聲明：轉載此文是出于傳遞更多信息之目的。若有來源标注錯誤或侵... 2022-10-28
生活手術成功簡單祝福的話
手術成功簡單祝福的話?深深的祝福堅強的父親手術成功還有那些抗癌勇士早日康複，今天小編就來說說關于手術成功簡單祝福的話?下面更多詳細答案一起來看看吧!手術成功簡單祝福的話深深的祝福堅強的父親手術成功！還有那些抗癌勇士早日康複！喝藥，雖然苦了點... 2022-06-12
生活公務員丈夫遺棄患抑郁症妻子
文：青梅煮酒圖：來自網絡最近這段時間，極端天氣頻繁出現。在網上看到河北保定六月二十三日刮起大風，在視頻中看到真的是飛沙走石，那情景宛如世界末日。我們這裡倒是沒有大風，但已經連續一個星期四十攝氏度以上的高溫。在這個溫度下出門都需要勇氣，更别說... 2023-02-22
生活哪一年凱越值得購買
[資訊-牛車網]5月21日，上汽通用将一款曾經創造過銷量奇迹的車型複活了。沒錯，它就是“神車”凱越。2016年8月8日，随着最後一輛凱越的下線，也宣告其結束了在華銷售十三年的征程。在這長達十三年的日子裡，我們也一起見證了其累計268萬台的奇... 2023-01-23
生活種植頭發靠譜麼
除了愛情，還有一種東西無論貧窮還是富有，都會如影随形，伴你左右……這就是脫發！脫發對于人的形象影響十分嚴重，甚至還能“趕跑”你的愛情！還有，現在通過種植頭發，可以很好的解決脫發問題，讓生活和事業順利，愛情也重新歸來。那麼，種植頭發有用嗎？對... 2023-02-11
生活最新3月20日全國銅業廠家收購價格
長江現貨1#銅價：72940元/噸，跌910元/噸無氧銅絲(硬)：74100元/噸，跌910元/噸漆包線價：78140元/噸，跌910元/噸A00鋁價：20300元/噸，跌420元/噸廣東現貨1#銅價：72650元/噸，跌850元/噸A00... 2022-11-15
生活綠草如茵風吹草低見牛羊
#頭号周刊#抄書打卡第九十二天今天是2022年8月12日，氣溫24℃—36℃，天氣悶熱，節氣雖然已經是立秋，但是天氣沒有一絲涼意。特别是中午時間，空氣中一點風都沒有，房子裡熱得像燒透了的火籠，使人喘不過氣來。吃個飯，全身就已經被汗水濕透了，... 2022-12-11
生活敦煌莫高窟在甘肅哪個城市
, 2023-03-22
生活有什麼辦法可以下山
（本文首發于“劉潤”公衆号，和160萬讀者一起洞察商業本質，歡迎訂閱）下山那天，師父給了我8個錦囊，對我說：遇事不決，打開看看。但是，但是，但是。我一下子沒忍住，全給打開了。和你分享。—1—學醫三年，覺天下無不可治之病行醫三年，覺天下無可治... 2022-12-08
生活黃豆浸泡四五個小時可以打豆漿嗎
很多人在早上喜歡吃一根油條和一杯豆漿，這樣其實也是很有營養的，很多人也會自己在家裡面打，但是自己在家裡面做的時候，總會覺得它不好喝，其實打豆漿也有技巧，我家樓底下的早餐店，經營這家小店的人叫何師傅，專門煮各種粥和豆漿有20餘年，喝一口，感覺... 2022-12-23
生活京東跨境電商怎麼進入中國
【億邦原創】被稱為“全球電商新一極”的Shopify，正在重新理解和打開中國市場。這一次，它不光面向出海的中國商家，還要把海外商家帶入中國。更重要的是，它找到一個本土盟友來一起完成。日前，京東集團宣布與Shopify達成戰略合作，成為Sho... 2023-03-09
生活瑪格麗特的做法
瑪格麗特的做法?用料：低筋面粉85g、玉米澱粉85g、黃油85g、糖粉40g、鹽1g、熟蛋黃2個，今天小編就來聊一聊關于瑪格麗特的做法?接下來我們就一起去研究一下吧!瑪格麗特的做法用料：低筋面粉85g、玉米澱粉85g、黃油85g、糖粉40g... 2022-07-08
生活不蔓不枝的蔓什麼意思
不蔓不枝的蔓什麼意思?不蔓不枝的蔓釋義：藤蔓出自：宋周敦頤《愛蓮說》：“中通外直，不蔓不枝”原意是說蓮莖不蔓延，也不分枝後來多用以稱贊文章簡潔，不拖泥帶水，今天小編就來說說關于不蔓不枝的蔓什麼意思?下面更多詳細答案一起來看看吧!不蔓不枝的蔓... 2022-06-06
生活明教教主張無忌從明朝活到現代
任何小說都有好人、壞人之分，武俠小說也不例外。尤其是擅長刻畫人物的金庸，在他架構的爾虞我詐的江湖世界裡，好壞之分已經升華到了門派之争。一、正派與反派在《笑傲江湖》裡，由于泰山派、衡山派、華山派、嵩山派、恒山派結成聯盟，他們又是以劍術作為主要... 2023-02-12
生活支付寶内測新功能在哪裡
近日，支付寶APP迎來了10.3.50新版更新，iOS和安卓用戶均可以升級體驗。更新日志顯示，該版本主要解決部分已知問題，優化多項細節，體驗更流暢等，并沒有提示加入新功能。不過，根據網友反饋，支付寶正在内測「服務管理」新功能，部分網友升級後... 2023-03-30
生活非洲河馬的海外生活
"喲，真的假的，百色也有動物園？"這話裡帶着嚴重的不可思議的意思。“在哪呢？”這聲音裡已經迫不及待了。“裡面有動物多嗎？”這個更急切，已經想要跟動物們見面了！桂西小城百色，來了稀客啦！它就是，來自非洲的河馬先生！！！“什麼！還有6000多斤... 2023-03-01
生活簡單日常護膚的正确順序
Hi~美少女們晚上好呀~之前給寶寶們科普過「化妝的順序」，沒有看過的戳~☟純幹貨│适合化妝小白的超詳細化妝步驟有很多留言說，護膚品的使用順序也不太清楚！精華要用在哪一步？白天和晚上的護膚步驟是一樣的嗎？求科普！~今天，毛戈平化妝學校的小編就... 2022-11-15
生活 50歲後一天要鍛煉幾個小時好呢
“40歲前必須鍛煉，50歲前适當鍛煉，60歲後不鍛煉、多保養。”這句看似“不走尋常路”的話，出自國家級名中醫徐再春。徐老在接受《杭州日報》采訪時表示，自己見過很多在養生道路上走偏的人。尤其是上了年紀的人，身患慢病還拼命鍛煉；而不到40歲的年... 2023-02-27
生活瓶裝水開了後多久不能喝
水是生命的源泉，人想要活着就離不開水，我們可以一周不吃飯，但不能超過三天不喝水，陷在困境的人，每個人的想法都是要尋找水源，這也能看出水對身體有多重要。對于人體來說，每天都要保持1500毫升左右的飲水量，水分過少，身體容易出問題，影響健康。我... 2023-01-26
生活北京cbd效果圖最新
北京是我國首都，它的城市建設方面也是我國毋庸置疑的天花闆，其中最具代表性的中央商務區北京也擁有多個，比如國貿CBD、望京CBD、麗澤CBD等。其中位于東三環也就是故宮正東方向的國貿中央商務區最為耀眼，可以說它無論從質感還是氣勢上來說都是全國... 2023-01-28
生活地獄級難度的手遊
點評：遊戲沿用了原版的人氣角色思黛拉和她的夥伴們，可愛範滿滿的。近期，憤怒的小鳥系列新作《憤怒的小鳥思黛拉泡泡》已全面上線雙平台，所有角色及故事背景都沿用了都延續怒鳥思黛拉，本次采用的是泡泡龍遊戲方式，不過玩法多了起來。對此類遊戲的玩法相信... 2022-11-21
生活煮鹌鹑蛋需要煮幾分鐘
煮鹌鹑蛋需要煮幾分鐘?逛菜市場的時候看到賣雞蛋的攤子上有鹌鹑蛋賣,當時馬上想到了小時候吃的袋裝的鐵蛋零食，那兒時記憶中讓人懷念的味道，懷念不如行動，趕緊買上一斤的鹌鹑蛋自己回家去做喲鹌鹑蛋是一種很好的滋補品，被認為是“動物中的人參”，宜常食... 2023-01-28

tft每日頭條

> 生活

> 最短路徑問題的原理及畫法

最短路徑問題的原理及畫法

相关生活资讯推荐

热门生活资讯推荐

网友关注