java有沒(méi)有這樣的算法 java最短路徑算法如何實(shí)現(xiàn)有向任意兩點(diǎn)的最短路徑？

java最短路徑算法如何實(shí)現(xiàn)有向任意兩點(diǎn)的最短路徑？Dijkstra算法是一種典型的最短路徑路由算法，用于計(jì)算從一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑。主要特征是從起點(diǎn)向外擴(kuò)展，直到終點(diǎn)。Dijkstra一

java最短路徑算法如何實(shí)現(xiàn)有向任意兩點(diǎn)的最短路徑？

1.聲明兩組，打開(kāi)和關(guān)閉。open用于存儲(chǔ)未遍歷的節(jié)點(diǎn)，close用于存儲(chǔ)已遍歷的節(jié)點(diǎn)。

2.在初始階段，將初始節(jié)點(diǎn)置于關(guān)閉狀態(tài)，將所有其他節(jié)點(diǎn)置于打開(kāi)狀態(tài)。

3.以初始節(jié)點(diǎn)為中心逐層向外遍歷，得到離指定節(jié)點(diǎn)最近的子節(jié)點(diǎn)，放入close并重新計(jì)算路徑，直到close包含所有子節(jié)點(diǎn)編碼。例子如下:Node對(duì)象用于封裝節(jié)點(diǎn)信息，包括名稱(chēng)和子節(jié)點(diǎn)[Java]view plain copy public class

用最通俗易懂的解釋一致哈希算法；

首先要明確，一般的哈希算法在取模的時(shí)候往往和實(shí)際應(yīng)用有關(guān)！

比如使用nginx hash時(shí)，會(huì)根據(jù)后臺(tái)應(yīng)用服務(wù)器的數(shù)量取模。比如后臺(tái)有四個(gè)應(yīng)用，通過(guò)hash(key)%4 =(0，1，2，3)可以得到其中一個(gè)的具體標(biāo)簽。此時(shí)，如果后臺(tái)應(yīng)用需要擴(kuò)展，哈希算法將改為hash (key) % 6 = (0，1)。它不 t把請(qǐng)求分發(fā)到6臺(tái)不同的機(jī)器上看起來(lái)問(wèn)題不大，但是如果我們把場(chǎng)景切換到一個(gè)數(shù)據(jù)庫(kù)按照業(yè)務(wù)主鍵business_no進(jìn)行哈希的子數(shù)據(jù)庫(kù)和子表結(jié)構(gòu)，切換之后因?yàn)楣Ｋ惴ǖ淖兓紨?shù)據(jù)下降到4，但是哈希結(jié)果是5，那么原始數(shù)據(jù)可以 t被發(fā)現(xiàn)，并且存在數(shù)據(jù)查詢(xún)錯(cuò)誤問(wèn)題！

但如果在redis上出現(xiàn)上述問(wèn)題，由于大量數(shù)據(jù)未命中，大量查詢(xún)降落在底層數(shù)據(jù)庫(kù)上，嚴(yán)重的話會(huì)出現(xiàn)緩存雪崩問(wèn)題，導(dǎo)致數(shù)據(jù)庫(kù)系統(tǒng)甚至整個(gè)系統(tǒng)的雪崩；

讓 下面我們來(lái)詳細(xì)說(shuō)說(shuō)一致哈希算法(以redis存儲(chǔ)為例)解決上述問(wèn)題的方法:

一致哈希算法，不管你有多少應(yīng)用，都是以2 ^ 32(2的32次方)為模數(shù)，把0和2 ^ 32-1首尾相連形成一個(gè)環(huán)，這樣所有使用一致哈希算法的數(shù)據(jù)都是大概率一致的。落在這枚戒指上；

掉在環(huán)上的數(shù)據(jù)最后怎么會(huì)在不同的redis服務(wù)器上？無(wú)論我們使用redis服務(wù)器的IP還是域名，它都是一個(gè)唯一的標(biāo)識(shí)符。很好理解，通過(guò)計(jì)算hash值，同樣落在這個(gè)環(huán)上(ABCD服務(wù)器節(jié)點(diǎn))，然后規(guī)定落在環(huán)上的數(shù)據(jù)順時(shí)針旋轉(zhuǎn)，存儲(chǔ)在我們遇到的第一個(gè)節(jié)點(diǎn)(服務(wù)器)上。如下圖所示:

使用一致哈希后，我們服務(wù)器的擴(kuò)展也將變得非常容易。如果監(jiān)測(cè)到一個(gè)節(jié)點(diǎn)(D)的壓力相對(duì)較高，則通過(guò)計(jì)算哈希值，在這個(gè)節(jié)點(diǎn)的上游逆時(shí)針?lè)较蛟黾右粋€(gè)服務(wù)器E(A和D之間)，如下圖所示:

這時(shí)，如果有請(qǐng)求進(jìn)來(lái)，整個(gè)環(huán)中只有A和E之間的數(shù)據(jù)可以 t被獲取，會(huì)對(duì)下層數(shù)據(jù)庫(kù)產(chǎn)生影響，其他所有數(shù)據(jù)不會(huì)有任何影響，所以使用一致哈希擴(kuò)展非常方便！

一致性哈希存在的問(wèn)題:

1.雪崩效應(yīng):假設(shè)我們不 t有類(lèi)似上面說(shuō)的監(jiān)控，或者A節(jié)點(diǎn)(B)的數(shù)據(jù)激增，在我們做出反應(yīng)之前，這個(gè)節(jié)點(diǎn)此時(shí)宕機(jī)，那么所有的數(shù)據(jù)請(qǐng)求都會(huì)迅速落在A身上，A不僅要承擔(dān)自己的數(shù)據(jù)，還要承擔(dān)B ;s，而且肯定會(huì)馬上崩潰，最后整個(gè)緩存系統(tǒng)都會(huì)產(chǎn)生雪崩效應(yīng)！

2.分布不均勻:上面的例子對(duì)于哈希算法來(lái)說(shuō)太理想化了。比如四臺(tái)ABCD服務(wù)器的hash值剛好是1，2，3，4，這意味著所有hash值在(4，2 32-1)范圍內(nèi)的數(shù)據(jù)都會(huì)落在一個(gè)服務(wù)上，這也將是災(zāi)難性的。。。

那么我們?nèi)绾谓鉀Q這種非常不均勻的數(shù)據(jù)分布呢？

解決方案:最好的方法是添加虛擬節(jié)點(diǎn)。截圖如下:

ABCD向每個(gè)服務(wù)器A、B、C和D添加了一個(gè)虛擬節(jié)點(diǎn)(或多個(gè)虛擬節(jié)點(diǎn)),這意味著節(jié)點(diǎn)A現(xiàn)在可以接受從B2-A1加上C1到A2的數(shù)據(jù)。假設(shè)服務(wù)A宕機(jī)，A1的數(shù)據(jù)會(huì)落在C2(也就是C)，A2的數(shù)據(jù)會(huì)落在D1(也就是D)，這意味著隨著崩潰服務(wù)器的增加，相應(yīng)的數(shù)據(jù)會(huì)更加分散。

通過(guò)以上案例，我們可以看到，一致哈希遵循以下原則:①平衡:將數(shù)據(jù)盡可能均勻地分布在整個(gè)哈希環(huán)上，

(2)單調(diào)性:在擴(kuò)展時(shí)，會(huì)保證原始數(shù)據(jù)盡可能少的落在新的節(jié)點(diǎn)上。

3.去中心化:盡量避免相同的內(nèi)容落在不同的節(jié)點(diǎn)上！

一致哈希的原理很簡(jiǎn)單，但是一致哈希算法在redis集群、數(shù)據(jù)庫(kù)子數(shù)據(jù)庫(kù)子表等場(chǎng)景中應(yīng)用廣泛，解決了數(shù)據(jù)分布不均勻、擴(kuò)展困難等問(wèn)題，是大規(guī)模集群中的優(yōu)秀算法！

本文個(gè)人感受這個(gè)解釋相當(dāng)容易理解。如果你有朋友不喜歡。;我不明白，你可以私下信任我。我會(huì)再解釋一遍。后期會(huì)有更多的技術(shù)分享，請(qǐng)繼續(xù)關(guān)注。謝謝你。。。