最短路径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知识，也可以点击本站的其他文章进行学习。