最短路徑java
A. 哈密頓迴路 java程序
最短路徑問題分兩類，一類是單源最短路徑問題，就是從指定頂點出發到其他各點的最短距離，還有一類是
每兩個遲毀皮頂點之間的最短距離，當然第二類也可以通過對每個頂點做一次單源最短路徑求解，但是還有一種更優雅的方法（Floyd演算法），這種方法一般使用相鄰矩陣的實現方式，對每個頂點看它是不是能作為其它沒兩對頂點間的碼差直接中間節點，如果能，那麼再看是不是通過它的兩兩頂點的距離是不是減小了，若果是就更新這兩對頂點間的距離，這樣通過每次「余好貪婪的」找出局部最優解來得到全局最優解，可以算是一個動態規劃的解法。
首先我們需要一個輔助類來保存距離，以及回溯路徑的類：
public static class Dist implements Comparable<Dist>
{
public int preV;
public int curV;
public int distance;
public Dist(int v)
{
this.curV=v;
this.preV=-1;
this.distance=Integer.MAX_VALUE;
}
@Override
public int compareTo(Dist other) {
return distance-other.distance;
}
}
下面給出第二類最短路徑的解法（Floyd演算法）Java實現：
@Override
public void floyd(Dist[][] dists) {
for(int i=0;i<numVertexes;i++)
{
dists[i]=new Dist[numVertexes];
for(int j=0;j<numVertexes;j++)
{
dists[i][j]=new Dist(-1);//
dists[i][j].preV=-1;
if(i==j)
dists[i][j].distance=0;
else
dists[i][j].distance=Integer.MAX_VALUE;
}
}
for(int v=0;v<numVertexes;v++)
{
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
int to=toVertex(e);
dists[v][to].distance=e.getWeight();
dists[v][to].preV=v;
}
}
for(int v=0;v<numVertexes;v++)
{
for(int i=0;i<numVertexes;i++)
for(int j=0;j<numVertexes;j++)
{
if((dists[i][v].distance!=Integer.MAX_VALUE)&&(dists[v][j].distance!=Integer.MAX_VALUE)&&(dists[i][v].distance+dists[v][j].distance<dists[i][j].distance))
{
dists[i][j].distance=dists[i][v].distance+dists[v][j].distance;
dists[i][j].preV=v;
}
}
}
}
/**
* A Graph example
* we mark the vertexes with 0,1,2,.14 from left to right , up to down
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
*
*/
public static void testFloyd() {
DefaultGraph g=new DefaultGraph(15);
g.setEdge(0, 1, 8);
g.setEdge(1, 0, 8);//its a undirected graph
g.setEdge(1, 2, 4);
g.setEdge(2, 1, 4);
g.setEdge(2, 3, 2);
g.setEdge(3, 2, 2);
g.setEdge(3, 4, 7);
g.setEdge(4, 3, 7);
g.setEdge(0, 5, 3);
g.setEdge(5, 0, 3);
g.setEdge(1, 6, 3);
g.setEdge(6, 1, 3);
g.setEdge(2, 7, 1);
g.setEdge(7, 2, 1);
g.setEdge(3, 8, 2);
g.setEdge(8, 3, 2);
g.setEdge(4, 9, 5);
g.setEdge(9, 4, 5);
g.setEdge(5, 6, 2);
g.setEdge(6, 5, 2);
g.setEdge(6, 7, 6);
g.setEdge(7, 6, 6);
g.setEdge(7, 8, 7);
g.setEdge(8, 7, 7);
g.setEdge(8, 9, 2);
g.setEdge(9, 8, 2);
g.setEdge(10, 5, 6);
g.setEdge(5, 10, 6);
g.setEdge(11, 6, 1);
g.setEdge(6, 11, 1);
g.setEdge(12, 7, 1);
g.setEdge(7, 12, 1);
g.setEdge(13, 8, 1);
g.setEdge(8, 13, 1);
g.setEdge(14, 9, 2);
g.setEdge(9, 14, 2);
g.setEdge(10, 11, 5);
g.setEdge(11, 10, 5);
g.setEdge(11, 12, 1);
g.setEdge(12, 11, 1);
g.setEdge(12, 13, 3);
g.setEdge(13, 12, 3);
g.setEdge(13, 14, 3);
g.setEdge(14, 13, 3);
g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
Dist[][] dists=new Dist[15][15];
g.floyd(dists);
System.out.println("Shortes path from S-T ("+dists[0][14].distance+")is:");
Stack<String> stack=new Stack<String>();
int i=0;
int j=14;
while(j!=i)
{
stack.push(g.getVertexLabel(j));
j=dists[i][j].preV;
}
stack.push(g.getVertexLabel(i));
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();
}
單源最短路徑問題的解法有Dijstra提出，所以也叫Dijstra演算法。
它把頂點分為兩個集合一個是已求出最短距離的頂點集合V1，另一類是暫未求出的頂點集合V2，而可以證明下一個將求出來（V2中到出發點最短距離值最小）的頂點的最短路徑上的頂點除了該頂點不在V1中外其餘頂點都在V1中。
如此，先把出發點放入V1中（出發點的最短距離當然也就是0），然後每次選擇V2中到出發點距離最短的點加入V1，並把標記改點的最短距離.直到V2中沒有頂點為止，詳細的形式化證明見：
Dijstra演算法證明
這里的實現我們使用最小值堆來每次從V2中挑出最短距離。
先給出最小值堆的實現：
package algorithms;
import java.lang.reflect.Array;
public class MinHeap<E extends Comparable<E>>
{
private E[] values;
int len;
public MinHeap(Class<E> clazz,int num)
{
this.values=(E[])Array.newInstance(clazz,num);
len=0;
}
public final E removeMin()
{
E ret=values[0];
values[0]=values[--len];
shift_down(0);
return ret;
}
//insert to tail
public final void insert(E val)
{
values[len++]=val;
shift_up(len-1);
}
public final void rebuild()
{
int pos=(len-1)/2;
for(int i=pos;i>=0;i--)
{
shift_down(i);
}
}
public final boolean isEmpty()
{
return len==0;
}
/**
* When insert element we need shiftUp
* @param array
* @param pos
*/
private final void shift_up(int pos)
{
E tmp=values[pos];
int index=(pos-1)/2;
while(index>=0)
{
if(tmp.compareTo(values[index])<0)
{
values[pos]=values[index];
pos=index;
if(pos==0)break;
index=(pos-1)/2;
}
else break;
}
values[pos]=tmp;
}
private final void shift_down(int pos)
{
E tmp=values[pos];
int index=pos*2+1;//use left child
while(index<len)//until no child
{
if(index+1<len&&values[index+1].compareTo(values[index])<0)//right child is smaller
{
index+=1;//switch to right child
}
if(tmp.compareTo(values[index])>0)
{
values[pos]=values[index];
pos=index;
index=pos*2+1;
}
else
{
break;
}
}
values[pos]=tmp;
}
}
下面是基於最小值堆的最短路勁演算法以及一個測試方法：
public void dijstra(int fromV,Dist[] dists)
{
MinHeap<Dist> heap=new MinHeap<Dist>(Dist.class,numVertexes*2);
for(int v=0;v<numVertexes;v++)
{
dists[v]=new Dist(v);
}
Arrays.fill(visitTags, false);
dists[fromV].distance=0;
dists[fromV].preV=-1;
heap.insert(dists[fromV]);
int num=0;
while(num<numVertexes)
{
Dist dist=heap.removeMin();
if(visitTags[dist.curV])
{
continue;
}
visitTags[dist.curV]=true;
num++;
for(Edge e=firstEdge(dist.curV);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)]&&e.getWeight()+dist.distance<dists[toVertex(e)].distance)
{
dists[toVertex(e)].distance=e.getWeight()+dist.distance;
dists[toVertex(e)].preV=dist.curV;
heap.insert(dists[toVertex(e)]);
}
}
}
}
/**
* A Graph example
* we mark the vertexes with 0,1,2,.14 from left to right , up to down
* S-8-B-4-A-2-C-7-D
* | | | | |
* 3 3 1 2 5
* | | | | |
* E-2-F-6-G-7-H-2-I
* | | | | |
* 6 1 1 1 2
* | | | | |
* J-5-K-1-L-3-M-3-T
*
*/
public static void testDijstra()
{
DefaultGraph g=new DefaultGraph(15);
g.setEdge(0, 1, 8);
g.setEdge(1, 0, 8);//its a undirected graph
g.setEdge(1, 2, 4);
g.setEdge(2, 1, 4);
g.setEdge(2, 3, 2);
g.setEdge(3, 2, 2);
g.setEdge(3, 4, 7);
g.setEdge(4, 3, 7);
g.setEdge(0, 5, 3);
g.setEdge(5, 0, 3);
g.setEdge(1, 6, 3);
g.setEdge(6, 1, 3);
g.setEdge(2, 7, 1);
g.setEdge(7, 2, 1);
g.setEdge(3, 8, 2);
g.setEdge(8, 3, 2);
g.setEdge(4, 9, 5);
g.setEdge(9, 4, 5);
g.setEdge(5, 6, 2);
g.setEdge(6, 5, 2);
g.setEdge(6, 7, 6);
g.setEdge(7, 6, 6);
g.setEdge(7, 8, 7);
g.setEdge(8, 7, 7);
g.setEdge(8, 9, 2);
g.setEdge(9, 8, 2);
g.setEdge(10, 5, 6);
g.setEdge(5, 10, 6);
g.setEdge(11, 6, 1);
g.setEdge(6, 11, 1);
g.setEdge(12, 7, 1);
g.setEdge(7, 12, 1);
g.setEdge(13, 8, 1);
g.setEdge(8, 13, 1);
g.setEdge(14, 9, 2);
g.setEdge(9, 14, 2);
g.setEdge(10, 11, 5);
g.setEdge(11, 10, 5);
g.setEdge(11, 12, 1);
g.setEdge(12, 11, 1);
g.setEdge(12, 13, 3);
g.setEdge(13, 12, 3);
g.setEdge(13, 14, 3);
g.setEdge(14, 13, 3);
g.assignLabels(new String[]{"S","B","A","C","D","E","F","G","H","I","J","K","L","M","T"});
Dist[] dists=new Dist[15];
g.dijstra(0, dists);
System.out.println("Shortes path from S-T ("+dists[14].distance+")is:");
Stack<String> stack=new Stack<String>();
for(int v=dists[14].curV;v!=-1;v=dists[v].preV)
{
stack.push(g.getVertexLabel(v));
}
while(!stack.isEmpty())
{
System.out.print(stack.pop());
if(!stack.isEmpty())System.out.print("->");
}
System.out.println();
}
B. Floyd演算法是什麼
Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。
通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最後又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。
採用的是(鬆弛技術)，對在i和j之間的所有其他點進行一次鬆弛。所以時間復雜度為O(n^3); 其狀態轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]} map[i,j]表示i到j的最短距離 K是窮舉i,j的斷點 map[n,n]初值應該為0，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路
C. Java網路編程基本概念是什麼
1、Java網路編程基本概念——主機的網路層
主機網路層定義特定網路介面(如乙太網或WiFi天線)如何通過物理連接將IP數據報發送到本地網路或世界其他地方。在主機網路層中，連接不同計算機的硬體部分(電纜、光纖、無線電波或煙霧信號)有時被稱為網路的物理層。Java程序員不需要擔心這一層，除非出現錯誤，例如計算機後面的插頭脫落或有人切斷了您與外部世界之間的T-1線。換句話說，Java將永遠看不到物理層。
2、Java網路編程基本概念——網路層
Internet層的下一層是主機網路層，這是Java程序員需要考慮的第一層。網際網路層協議定義了數據位和位元組如何組織成更大的組，稱為包，也定義了不同計算機互相查找的定址機制。Internet Protocol (IP)是世界上使用最廣泛的Internet層協議，也是Java唯一了解的Internet層協議。
網際網路協議基本上是兩種協議:IPV4使用32位地址，IPV6使用128位地址，並增加了技術特性來幫助路由。這是兩種完全不同的網路協議，如果沒有特殊的網關/隧道協議，它們甚至不能在同一網路上互操作，但是Java向您隱藏了幾乎所有這些差異。
除了路由和定址之外，網際網路層的第二個作用是使不同類型的主機網路層能夠彼此對話。網際網路路由器在WiFi和乙太網、乙太網和DSL、DSL和光纖往返協議之間進行交換。沒有網際網路層或類似的分層，每台計算機只能與同一類型網路上的其他計算機通信。網際網路層負責使用適當的協議將異類網路彼此連接起來。
3、Java網路編程基本概念——傳輸層
原始數據報有一些缺點。最明顯的缺點是無法保證可靠的傳輸，即使可以保證，也可能在傳輸過程中被損壞。頭檢查只能檢測頭中的損壞，而不能檢測數據報的數據部分。最後，即使數據報沒有損壞地到達了它的目的地，它也可能不能按照發送的順序到達。
傳輸層負責確保按發送的順序接收數據包，確保沒有數據丟失或銷毀。如果數據包丟失，傳輸層要求發送方重新傳輸該數據包。為此，IP網路向每個數據報添加了一個額外的頭，其中包含更多信息。
這個級別有兩個主要協議。第一個是傳輸控制協議(TCP)，這是一個昂貴的協議，允許丟失或損壞的數據按照發送順序重新傳輸。第二個協議是用戶數據報協議(User Datagram Protocol, UDP)，它允許接收方檢測損壞的數據包，而不保證它們按照正確的順序發送(或者根本不發送)。然而，UDP通常比TCP快。TCP被稱為可靠協議。UDP是不可靠的。
4、Java網路編程基本概念——應用程序層
向用戶交付數據的層稱為應用層。以下三個層定義如何將數據從一台計算機傳輸到另一台計算機。應用層決定數據傳輸後的操作。有HTTP為用戶Web, SMTP, POP, IMAP為用戶電子郵件;FSP, TFTP用於文件傳輸，NFS用於文件訪問;文件共享使用Gnutella和BitTorrent;會話發起協議(SIP)和Skype用於語音通信。此外，您的程序可以在必要時定義自己的應用程序級協議。(頁面)
5、Java網路編程基本概念——IP、TCP、UDP
IP被設計成允許任意兩點之間有多條路由，繞過損壞的路由器來路由數據包。由於兩點之間有多條路由，而且由於網路流量或其他因素，它們之間的最短路徑可能會隨著時間而變化，因此構成特定數據流的數據包可能不會走同一條路由。即使它們全部到達，也可能不是按照它們被發送的順序到達的。為了改進這一基本機制，TCP被放置在IP上，以便連接的兩端可以確認收到的IP數據包，並請求重傳丟失或損壞的數據包。此外，TCP允許接收端上的數據包按照發送的順序重新分組。
然而，TCP有很多開銷。因此，如果單個數據包的丟失不會完全破壞數據，那麼可以使用UDP發送數據包，而不需要TCP提供的保證。UDP是一種不可靠的協議。它不能保證信息包將到達它們的目的地，或者它們將以它們被發送的相同順序到達。
6、Java網路編程基本概念——IP地址和域名
IPv4網路上的每台計算機都有一個4位元組的數字ID。通常在一個點上以四段格式寫，比如192.1.32.90，每個數字是一個無符號位元組，范圍從0到255。IPv4網路上的每台計算機都有一個唯一的四段地址。當數據通過網路傳輸時，包的報頭包括要發送到的機器的地址(目的地址)和要發送到的機器的地址(源地址)。路由上的路由器通過檢查目的地址來選擇發送包的最佳路徑。包含源地址是為了讓收件人知道該對誰進行回復。
雖然計算機可以很容易地處理數字，但人類並不擅長記住它們。因此，域名系統(DNS)被開發出來，用來將容易記住的主機名(如www.12345.com)轉換成數字互聯網地址(如208.201.243.99)。當Java程序訪問網路時，它們需要同時處理數字地址和相應的主機名。這些方法由java.net.InetAddress類提供。
7、Java網路編程基本概念——港口
如果每台計算機一次只做一件事，地址就足夠了。但是現代計算機同時做許多不同的事情。電子郵件需要與FTP請求分開，而FTP請求也需要與Web通信分開。這是通過埠完成的。具有IP地址的每台計算機有數千個邏輯埠(確切地說，每個傳輸層協議有65,535個埠)。這些只是計算機內存中的抽象，不代表任何物理對象，不像USB埠。每個埠在1到65535之間進行數字標識。每個埠可以分配給一個特定的服務。
8、Java網路編程基本概念——一個防火牆
在互聯網上有一些頑皮的人。要排除它們，通常需要在本地網路上設置一個接入點，並檢查進出該接入點的所有流量。位於網際網路和本地網路之間的一些硬體和軟體會檢查所有輸入和輸出的數據，以確保它是防火牆。防火牆通常是路由器的一部分，它將本地網路連接到更大的網際網路，並可以執行其他任務，如網路地址轉換。另外，防火牆可以是單獨的機器。防火牆仍然主要負責檢查進出其網路介面的數據包，根據一組規則接收或拒絕數據包。
本篇《什麼是Java網路編程基本概念?看完這篇文章你一定可以明白》到這里就已經結束了，小編一直認為，某一個編程軟體受歡迎是有一定原因的，首先吸引人的一定是其功能，環球網校的小編祝您java學習之路順利，如果你還想知道更多java知識，也可以點擊本站的其他文章進行學習。