的> 轉(zhuǎn)載請(qǐng)標(biāo)明出處，謝謝！
http://www.itdecent.cn/p/873f2d5b9ca1
關(guān)聯(lián)文章
冒泡、選擇排序 http://www.itdecent.cn/p/176b0b892591
棧和隊(duì)列 http://www.itdecent.cn/p/8cb602ef4e21
順序表、單雙鏈表 http://www.itdecent.cn/p/3aeb5998e79e
二叉樹(shù) http://www.itdecent.cn/p/de829eab944c
圖論 http://www.itdecent.cn/p/cf03e51a3ca2
算法 http://www.itdecent.cn/p/873f2d5b9ca1
Lcs算法
動(dòng)態(tài)規(guī)劃思想
經(jīng)常會(huì)遇到復(fù)雜問(wèn)題不能簡(jiǎn)單地分解成幾個(gè)子問(wèn)題，而會(huì)分解出一系列的子問(wèn)題。簡(jiǎn)單地采用把大問(wèn)題分解成子問(wèn)題，并綜合子問(wèn)題的解導(dǎo)出大問(wèn)題的解的方法，問(wèn)題求解耗時(shí)會(huì)按問(wèn)題規(guī)模呈冪級(jí)數(shù)增加。
為了節(jié)約重復(fù)求相同子問(wèn)題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問(wèn)題的解存于該數(shù)組 中，這就是動(dòng)態(tài)規(guī)劃法采用的基本方法
問(wèn)題描述
什么是最長(zhǎng)公共子序列呢?好比一個(gè)數(shù)列 S，如果分別是兩個(gè)或多個(gè)已知數(shù)列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則S 稱為已知序列的最長(zhǎng)公共子序列。
舉個(gè)例子，如：有兩條隨機(jī)序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，則它們的最長(zhǎng)公共子序列便是：4 5 5。
注意最長(zhǎng)公共子串（Longest CommonSubstring）和最長(zhǎng)公共子序列（LongestCommon Subsequence, LCS）的區(qū)別：子串（Substring）是串的一個(gè)連續(xù)的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡(jiǎn)略地說(shuō)，前者（子串）的字符的位置必須連續(xù)，后者（子序列LCS）則不必。比如字符串a(chǎn)cdfg同akdfc的最長(zhǎng)公共子串為df，而他們的最長(zhǎng)公共子序列是adf。LCS可以使用動(dòng)態(tài)規(guī)劃法解決。
解最長(zhǎng)公共子序列問(wèn)題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X的每一個(gè)子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列。X和Y的所有子序列都檢查過(guò)后即可求出X和Y的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1, 2, …, m}的一個(gè)子序列，因此，X共有2m個(gè)不同子序列（Y亦如此，如為2n），從而窮舉搜索法需要指數(shù)時(shí)間（2m * 2^n）?？紤]到搜索性能我們今天引出了一個(gè)動(dòng)態(tài)規(guī)劃算法來(lái)解決這個(gè)lcs算法的問(wèn)題。
下面開(kāi)始舉個(gè)例子說(shuō)明：
假設(shè)有兩個(gè)序列分別是X = ABCBDAB,Y = BDCABA
我們通過(guò)一個(gè)矩陣來(lái)說(shuō)明：
我們可以看到矩陣中有很多數(shù)字，暫且先不看灰色背景以及箭頭，我們先看下圖中矩陣的數(shù)字代表的是什么意思呢？
第一行和第一列統(tǒng)一填0，其他的相同的取左上角數(shù)字+1，不同的取左邊和上邊的最大者。
分析完數(shù)字的填寫(xiě)規(guī)則，現(xiàn)在討論下灰色數(shù)字。我們從右下角的4開(kāi)始分析，4所在的位置是Yj的A 和Xi的B，A≠B 所以4是左邊或者右邊推出來(lái)的（逆向推出數(shù)據(jù)）我們選擇頭部的4繼續(xù)分析，它的位置是Yj的A 和Xi的A，A=A ，所以它是由左上角的3推出的。繼續(xù)分析3的由來(lái)，3的位置是Yj的B 和Xi的D，B≠D。所以它是由頭部的3推出的。。。。。以此類推。就得到了圖中灰色區(qū)域。
那么我們要怎么得出他的最長(zhǎng)公共子序列呢?
我們通過(guò)第一輪已經(jīng)得到了灰色的區(qū)域，我們接下去通過(guò)灰色區(qū)域去分析：
右下角的4所在的位置表示A、B.因?yàn)锳≠B.所以舍棄。 頭部的4表示的是A和A，他們相等。所以得到一個(gè)A。以此類推，我們可以最終得到 A、B、C、B。那么倒序輸出就是BCBA，那么他們的最長(zhǎng)公共子序列就是BCBA.我們用肉眼去檢查下，結(jié)果也是對(duì)的。
我們一開(kāi)始分析的位置是最右小角的4，當(dāng)然你也可以從其他幾個(gè)4的位置開(kāi)始。圖中箭頭表示的就是不同的路徑分析的結(jié)果。
代碼分析：
public void getLCS(String x, String y) {
/*將字符串轉(zhuǎn)為字母保存*/
char[] a = x.toCharArray();
char[] b = y.toCharArray();
/*創(chuàng)建矩陣*/
int[][] array = new int[a.length + 1][b.length + 1];
int column = b.length + 1;
int row = a.length + 1;
/*將第一列、第一行設(shè)置0*/
for (int i = 0; i < column; i++) {
array[0][i] = 0;
}
for (int i = 1; i < row; i++) {
array[i][0] = 0;
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < column; j++) {
if(a[i-1]==b[j-1]){//如果相等，左上角加1填入
array[i][j]=array[i-1][j-1]+1;
}else{
array[i][j]=max(array[i-1][j],array[i][j-1]);
}
}
}
//打印
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
以上的操作是根據(jù)動(dòng)態(tài)規(guī)劃的方式填入數(shù)據(jù)
打印的結(jié)果：
和顯然和我們一開(kāi)始矩陣圖是相同的
接著將灰色部分的填入并輸出相應(yīng)的字母
Stack result = new Stack();
int i = row - 2;
int j = column -2 ;
while (i>=0 && j>=0){
if(a[i]==b[j]){
/*將當(dāng)前的字母儲(chǔ)存*/
result.push(a[i]);
i--;
j--;
}else{
/*注意數(shù)組和String中的位置有一位差*/
if(array[i+1][j+1-1]>array[i+1-1][j+1]){
j--;
}else{
i--;
}
}
}
System.out.println("-----");
while(!result.isEmpty()){
System.out.println(result.pop()+" ");
}
Kmp算法
KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡(jiǎn)稱KMP算法）。
字符串匹配。給你兩個(gè)字符串，尋找其中一個(gè)字符串是否包含另一個(gè)字符串，如果包含，返回包含的起始位置。
我們用一個(gè)簡(jiǎn)單的例子說(shuō)明一般的字符串匹配做法（暴力匹配）
以下例子來(lái)源：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個(gè)字符與搜索詞"ABCDABD"的第一個(gè)字符，進(jìn)行比較。因?yàn)锽與A不匹配，所以搜索詞后移一位。
因?yàn)锽與A不匹配，搜索詞再往后移。
就這樣，直到字符串有一個(gè)字符，與搜索詞的第一個(gè)字符相同為止。
接著比較字符串和搜索詞的下一個(gè)字符，還是相同。
直到字符串有一個(gè)字符，與搜索詞對(duì)應(yīng)的字符不相同為止。
這時(shí)，最自然的反應(yīng)是，將搜索詞整個(gè)后移一位，再?gòu)念^逐個(gè)比較。這樣做雖然可行，但是效率很差，因?yàn)槟阋?搜索位置"移到已經(jīng)比較過(guò)的位置，重比一遍。
一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)，你其實(shí)知道前面六個(gè)字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把"搜索位置"移回已經(jīng)比較過(guò)的位置，繼續(xù)把它向后移，這樣就提高了效率。
一般匹配字符串時(shí)，我們從目標(biāo)字符串str（假設(shè)長(zhǎng)度為n）的第一個(gè)下標(biāo)選取和ptr長(zhǎng)度（長(zhǎng)度為m）一樣的子字符串進(jìn)行比較，如果一樣，就返回開(kāi)始處的下標(biāo)值，不一樣，選取str下一個(gè)下標(biāo)，同樣選取長(zhǎng)度為n的字符串進(jìn)行比較，直到str的末尾（實(shí)際比較時(shí)，下標(biāo)移動(dòng)到n-m）。這樣的時(shí)間復(fù)雜度是 O(n*m) 。
KMP算法：可以實(shí)現(xiàn)復(fù)雜度為O(m+n)
為何簡(jiǎn)化了時(shí)間復(fù)雜度：
充分利用了目標(biāo)字符串ptr的性質(zhì)（比如里面部分字符串的重復(fù)性，即使不存在重復(fù)字段，在比較時(shí)，實(shí)現(xiàn)最大的移動(dòng)量）。
比如我們現(xiàn)在有一個(gè)字符串是"ababcabcbababcabacaba"
考察目標(biāo)字符串ptr：
ababcaba
這里我們要計(jì)算一個(gè)長(zhǎng)度為m的轉(zhuǎn)移函數(shù)next。
next數(shù)組的含義就是一個(gè)固定字符串的最長(zhǎng)前綴和最長(zhǎng)后綴相同的長(zhǎng)度。
比如：abcjkdabc，那么這個(gè)數(shù)組的最長(zhǎng)前綴和最長(zhǎng)后綴相同必然是abc。
cbcbc，最長(zhǎng)前綴和最長(zhǎng)后綴相同是cbc。
abcbc，最長(zhǎng)前綴和最長(zhǎng)后綴相同是不存在的。
注意最長(zhǎng)前綴：是說(shuō)以第一個(gè)字符開(kāi)始，但是不包含最后一個(gè)字符。
比如aaaa相同的最長(zhǎng)前綴和最長(zhǎng)后綴是aaa。
對(duì)于目標(biāo)字符串ptr，ababcaba ，長(zhǎng)度是8，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]，next[7]分別計(jì)算的是
a，ab，aba，abab，ababc，ababca，ababcab，ababcaba 的相同的最長(zhǎng)前綴和最長(zhǎng)后綴的長(zhǎng)度。由于a，ab，aba，abab，ababc，ababca，ababcab，ababcaba 的相同的最長(zhǎng)前綴和最長(zhǎng)后綴是“”，“”，“a”，“ab”，“”，“a”，“ab”，“aba”,所以next數(shù)組的值是[0,0,1,2,0,1,2,3]，這里0表示不存在，1,2,3分別代表匹配到的個(gè)數(shù)。
我們用圖例來(lái)進(jìn)一步說(shuō)明下：
(可以用一個(gè)count值統(tǒng)計(jì)相同的個(gè)數(shù))
1、我們需要2個(gè)指針j 和 i。j指向第一個(gè)位置，i指向第二個(gè)位置。
默認(rèn)next[0] = 0
2、因?yàn)閍≠b,所以b的next值next[1]是=0，此時(shí)j直接退回到第一個(gè)位置，i往后進(jìn)一位
3、因?yàn)樽詈笠晃缓偷谝晃坏腶相等，所以a的next值next[2]是 1，此時(shí)count = 1
4、同理b的next值next[3]是 2 , 此時(shí)count = 2
5、因?yàn)閍≠c,所以b的next值next[4]是=0，此時(shí)j直接退回到第一個(gè)位置，i往后進(jìn)一位 此時(shí)count = 0
6、兩個(gè)a相等，所以next[5]=1,此時(shí)count=1
7、同理對(duì)next[6],nexy[7]是同樣的操作
那么我得到上面這幾個(gè)數(shù)字的作用是什么呢？ 上面我們提過(guò)字符串匹配的暴力做法就是逐一匹配，遇到不同的重新回到原來(lái)的位置。而kmp算法就是為了盡可能的移動(dòng)最大偏移量。
我們的原來(lái)字符串是 "ababcabcbababcabacaba"
考察目標(biāo)字符串ptr是："ababcaba"。
用我們的肉眼幾乎一眼就可以看出目標(biāo)串一直匹配到倒數(shù)第二位，直到最后一位a與原字符串的c是不匹配的，所以移動(dòng)的時(shí)候并不需要一位一位的移動(dòng)。但是計(jì)算機(jī)畢竟是傻的，他怎么直到要移動(dòng)多少位置呢？
實(shí)際上我們有個(gè)規(guī)則。
移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
根據(jù)這個(gè)規(guī)則，我們進(jìn)行第一次移動(dòng)。移動(dòng)位數(shù) = 已匹配的個(gè)數(shù)7 - 對(duì)應(yīng)部分匹配值b對(duì)應(yīng)的next是2= 5
所以我們需要一次性移動(dòng)5位。
實(shí)際上kmp最核心的就是回退策略。用一句代碼表示就是 j = next[j-1].當(dāng)遇到不同的時(shí)候j的指針就回退到該位置。舉個(gè)例子：剛剛在比對(duì)過(guò)程中我們發(fā)現(xiàn)了a和c是不同的 那么此時(shí)比對(duì)的j的指針就是 j = next[7-1] = 2.所以我們就開(kāi)始有了上圖的從第二個(gè)位置開(kāi)始重新比對(duì)。
等下我們可以用代碼來(lái)表示。
好了繼續(xù)上面的移動(dòng)，上圖中我們發(fā)現(xiàn)a≠c，根據(jù)公式：移動(dòng)的位數(shù)= 2 - 0 = 2；
如果遇到第一個(gè)就不匹配的直接后移一位
繼續(xù)移動(dòng)一位
逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索（即找出全部匹配），移動(dòng)位數(shù) = 7 - 0，再將搜索詞向后移動(dòng)7位，這里就不再重復(fù)了。
代碼：
/**
*KMP算法得到數(shù)組
*/
public static int[] kmpNext(String dest){
int[] next=new int[dest.length()];
next[0]=0;
//開(kāi)始推出next
for(int i=1,j=0;i<dest.length();i++){
//3
while(j>0 && dest.charAt(j) != dest.charAt(i)){
j=next[j-1];
}
//1
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
//2
next[i]=j;
}
return next;
}
從代碼上我們可以到 如果是相同的 j++,加上外層的i++就相當(dāng)于剛剛圖例中的兩個(gè)指針同時(shí)后移一位。
如果是不同的j = next[i-1]。
完整代碼
@Test
public void addition_isCorrect() throws Exception {
String str="ababcabcbababcabacaba";
String dest="ababcaba";
int[] array=kmpNext(dest);
for (int i = 0; i <array.length ; i++) {
System.out.print(array[i]+" ");
}
// System.out.println(kmp(str,dest,array));
}
/**
*KMP算法得到數(shù)組
*/
public static int[] kmpNext(String dest){
int[] next=new int[dest.length()];
next[0]=0;
//開(kāi)始推出next
for(int i=1,j=0;i<dest.length();i++){
//3
while(j>0 && dest.charAt(j) != dest.charAt(i)){
j=next[j-1];
}
//1
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
//2
next[i]=j;
}
return next;
}
public static int kmp(String str,String dest,int[] next){
for(int i=0,j=0;i<str.length();i++){
while(j>0 && str.charAt(i) != dest.charAt(j)){
j=next[j-1];
}
if(str.charAt(i)==dest.charAt(j)){
j++;
}
if(j==dest.length()){//結(jié)束
return i-j+1;
}
}
return 0;
}
輸出結(jié)果是9,說(shuō)明在源字符串第幾個(gè)位置開(kāi)始匹配到數(shù)據(jù)。
Floyd算法
Floyd算法（Floyd-Warshall algorithm）又稱為弗洛伊德算法、插點(diǎn)法，是解決給定的加權(quán)圖中頂點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。
舉個(gè)例子說(shuō)明下：
我們用一個(gè)圖表示
生成他們的鄰接矩陣和路徑矩陣
其中d矩陣中的inf表示不能直接達(dá)到，比如v1->v3
接著我們修改d矩陣，然后把受影響的地方儲(chǔ)存在p矩陣中（修改p矩陣中對(duì)應(yīng)的數(shù)據(jù)）
什么意思呢？
首先我們以v0為跳板，從圖中我們可以看出v1->v2直接到達(dá)權(quán)重是4，如果以v0為跳板我們可以看到，v1->v0是2 v0->v2是1 3<4那么就修改d矩陣
再修改p矩陣，被0矩陣作為跳板修改過(guò)，則修改成0.同樣的inf位到達(dá)的也可以通過(guò)v0修改
接著我們以v1為跳板，發(fā)現(xiàn)沒(méi)有要修改的數(shù)據(jù)
以v2為跳板，我們發(fā)現(xiàn)v0->v3 = 5,而v0->v2->v3 = 4 v1->v3=7,而 v1->v2->v3 =6 同樣上面修改的原則對(duì)d,p矩陣進(jìn)行修改.
最后v3同樣不需要修改。所以以上的圖就是最短路徑d,p矩陣圖
那么這個(gè)代碼要怎么寫(xiě)呢？其實(shí)看懂了邏輯就很簡(jiǎn)單了。我們先拿v0為跳板的例子：
public static void printArray(int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println("---------------------");
}
//鄰接距陣
public static int[][] d = new int[][]{
{0, 2, 1, 5},
{2, 0, 4, I},
{1, 4, 0, 3},
{5, I, 3, 0}
};
public static int[][] p = new int[][]{
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3}
};
private static void floyd() {
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d[0].length; j++) {
if (d[i][j] > d[i][0] + d[0][j]) {
d[i][j] = d[i][0] + d[0][j];
p[i][j] = p[i][0];
}
}
}
}
打印的結(jié)果是
和我們一開(kāi)始做的兩個(gè)矩陣圖是一樣的
接著只要把0 再外面套個(gè)循環(huán)修改成動(dòng)態(tài)的就可以了
完整代碼是：
public class FloydTest {
private final static int I = Integer.MAX_VALUE;
@Test
public void test() {
floyd();
printArray(d);
printArray(p);
}
public static void printArray(int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j] + " ");
}
System.out.println();
}
System.out.println("---------------------");
}
//鄰接距陣
public static int[][] d = new int[][]{
{0, 2, 1, 5},
{2, 0, 4, I},
{1, 4, 0, 3},
{5, I, 3, 0}
};
public static int[][] p = new int[][]{
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3},
{0, 1, 2, 3}
};
private static void floyd() {
for (int k = 0; k < d.length; k++) {
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d[0].length; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[i][k];
}
}
}
}
}
}
輸出的結(jié)果是：
Dijkstra算法
迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。
它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。
Dijkstra算法介紹
算法特點(diǎn)：
迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無(wú)向圖的單源最短路徑問(wèn)題，算法最終得到一個(gè)最短路徑樹(shù)。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。
算法的思路
Dijkstra算法采用的是一種貪心的策略，聲明一個(gè)數(shù)組dis來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合：T，初始時(shí)，原點(diǎn) s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把dis[m]設(shè)為w（s, m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大。初始時(shí)，集合T只有頂點(diǎn)s。
然后，從dis數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中，OK，此時(shí)完成一個(gè)頂點(diǎn)，
然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過(guò)該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長(zhǎng)度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dis中的值。
然后，又從dis中找出最小值，重復(fù)上述動(dòng)作，直到T中包含了圖的所有頂點(diǎn)。
我們用圖來(lái)表示下算法實(shí)現(xiàn)的過(guò)程
假設(shè)我們有以上這個(gè)圖，圖中的數(shù)字表示的是權(quán)重。我們用一個(gè)矩陣來(lái)表示下：
{0,1,5,I,I,I,I,I,I},
{1,0,3,7,5,I,I,I,I},
{5,3,0,I,1,7,I,I,I},
{I,7,I,0,2,I,3,I,I},
{I,5,1,2,0,3,6,I,I},
{I,I,7,I,3,0,I,5,I},
{I,I,I,3,6,I,0,2,7},
{I,I,I,I,9,5,2,0,4},
{I,I,I,I,I,I,7,4,0}
其中數(shù)字代表的是權(quán)重，I表示無(wú)法到達(dá)。比如第一行的1，表示的是v0->v1的路徑是1，v0->v3無(wú)法到達(dá)。以此類推。
我們用兩個(gè)數(shù)組表示下：
權(quán)重?cái)?shù)組、路徑數(shù)組
以v0作為定點(diǎn)，v0可以直接到達(dá)的是v1和v2，我們選擇權(quán)重小的v1。
繼續(xù)，一旦頂點(diǎn)被選擇了，就往左邊推
圖中以v1為例子，v0->v1的權(quán)重是1，前驅(qū)是v0。
然后從左邊到右邊我們可以看到v1-v2是最小路徑，故刪除入度到v2比較大的路徑：
繼續(xù)往下操作，以下直接貼圖。
選擇v4
選擇v3
選擇5或6，這里我們選擇5
選擇6
選擇7
最后剩一個(gè)8
以上就是Dijkstra思想的圖例，如果還不懂，我們用一個(gè)簡(jiǎn)單的圖和一些簡(jiǎn)答的描述來(lái)說(shuō)明， Dijkstra的核心算法計(jì)算最短路徑實(shí)際上就是不斷選擇一個(gè)最短的路徑頂點(diǎn)歸到左邊，如下圖
比如v0到v4是最短的，那么把v4標(biāo)記成已選擇放入左邊
然后重新計(jì)算出各個(gè)權(quán)重，最后不斷的選擇出最短路徑歸入左邊已選擇的數(shù)組中。所以這個(gè)就是他的核心思想，通過(guò)這個(gè)思想我們可以通過(guò)代碼來(lái)表示
代碼：
public static final int I = 100;
int[][] array=new int[][]{
{0,1,5,I,I,I,I,I,I},
{1,0,3,7,5,I,I,I,I},
{5,3,0,I,1,7,I,I,I},
{I,7,I,0,2,I,3,I,I},
{I,5,1,2,0,3,6,I,I},
{I,I,7,I,3,0,I,5,I},
{I,I,I,3,6,I,0,2,7},
{I,I,I,I,9,5,2,0,4},
{I,I,I,I,I,I,7,4,0}
};
public void dijkstar(){
int k=0;//表示當(dāng)前正要處理的頂點(diǎn)Vk
//初始化相關(guān)的信息
int[] path=new int[9];//保存路徑
int[] weight=array[0];//保存權(quán)重
//定義一個(gè)數(shù)組來(lái)存放U和V兩個(gè)集合的信息
int[] flag=new int[9];
flag[0]=1;
//開(kāi)始邏輯,求VO到某個(gè)頂點(diǎn)的最短路徑
for(int v=1;v<9;v++){
//在能走的路徑中找到最短的一條
int min=I;
for(int i=0;i<9;i++){
if(flag[i]==0 && weight[i]<min){
k=i;//K為U集合到V集合中找到的頂點(diǎn)
min=weight[i];//min找到了最小值的位置
}
}
//從這個(gè)最短的路徑對(duì)應(yīng)的頂點(diǎn)開(kāi)始找下一輪
flag[k]=1;
//修正當(dāng)前最短路徑
for(int i=0;i<9;i++){
//如果經(jīng)過(guò)V頂點(diǎn)的路徑比現(xiàn)在的路徑短，新更新
if(flag[i]==0 && (min+array[k][i])<weight[i]){
weight[i]=min+array[k][i];//修改路徑長(zhǎng)度
path[i]=k;//保存前驅(qū)
}
}
}
for(int i=0;i<path.length;i++){
System.out.print(path[i]+" ");
}
System.out.println();
for(int i=0;i<weight.length;i++){
System.out.print(weight[i]+" ");
}
//打印結(jié)果
int v=8;
while(v!=0){
System.out.print(path[v]);
v=path[v];
}
}
@Test
public void test(){
dijkstar();
}
