有向图最短距离java

❶ java求坐标系中任意两点的距离取出最短距离

Point p1 = new Point(x1,y1);
Point p2 = new Point(x2,y2);
double gap = Math.sqrt(Math.pow(p1.y-p2.y,2) + Math.pow(p1.x-p2.x,2));

❷ 有向图求顶点出入度和最短路径Dijksatra算法。运行的出入度和求最短距离都有问题，请问出错在哪里

错在2处，一个图的初始化上，边的初始值应郑中该是无穷INF

G.edges[i][j]=0;改成G.edges[i][j]=INF;

另外一罩丛链个是函数outG显示邻接矩阵里，如果是INF则显物孙示∞

❸ 求如下有向图的关键路径以及任意两点之间的最短距离

用CPM算法求有向图的关键路径和用此敏高Dijkstra算法求有向图的最短路径的C语言程序如下

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <string.h>

#define MAX 20

#define INF 32767 // 此处修改最大值

#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))

#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))

typedef struct _graph{

char vexs[MAX]; // 顶点集合

int vexnum; // 顶点数

int edgnum; // 边数

int matrix[MAX][MAX]; // 邻接矩阵

}Graph, *PGraph;

// 边的结构体

typedef struct _EdgeData{

char start; // 边的起点

char end; // 边的终点

int weight; // 边的权重

}EData;

//指向节点的位置

int point_node(PGraph g,char c){

for(int i=0;i<g->vexnum;i++){

if(g->vexs[i]==c){

return i;

}

}

return -1;

}

PGraph create_graph(int b[][3],char a[],int n,int e){

char c1,c2; //边的2个顶点

PGraph g; //矩阵

g=(PGraph)malloc(sizeof(Graph));

//memset()第一个参数 是地址，第二个参数是开辟空间的初始值，第三个参数是开辟空间的大小

memset(g, 0, sizeof(Graph));

森尺printf("顶点个数: ");//顶点数

g->vexnum=n;

printf("%d ",g->vexnum);

printf("边个数: ");//边数

g->edgnum=e;

printf("%d ",g->edgnum);

//初始化顶点

for(int j=0;j<g->vexnum;j++){

g->vexs[j]=a[j];

}

for(int i=0;i<g->edgnum;i++){

int p1,p2;

c1=char(b[i][0]);

c2=char(b[i][1]);

p1=point_node(g, c1);

p2=point_node(g, c2);

if (p1==-1 || p2==-1){

printf("input error: invalid edge! ");

free(g);

continue;

}

g->matrix[p1][p2]=b[i][2];

}

for(int i=0;i<g->vexnum;i++){

for(int j=0;j<g->vexnum;j++){

if(g->matrix[i][j]==0)

g->matrix[i][j]=INF;

}

}

return g;

}

//关键路径的最短时间

//关键路径法（Critical Path Method，CPM）

void CPM_road(PGraph g){

int i,j;

int a[MAX]={0},b[MAX]={-10};

int max=0;//最长路径

for( i=0;i<g->vexnum;i++){//列数遍历

for( j=0;j<g->vexnum;j++){//行数遍历

//如果g->matrix[j][i]大于0，说明此顶拿模点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，

//加上g->matrix[j][i]的路径就是当前a[i]的路径

if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){

max=g->matrix[j][i]+a[j];

a[i]=max;

}

}

max=0;

}

//显示最长路径

printf("第一个顶点到每一个顶点的最长路径:");

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("V%d ",i+1);

}

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("%d ",a[i]);

}

printf(" ");

printf("最后一个顶点到每个顶点的最长路径:");

for( i=g->vexnum-1;i>=0;i--){ //列数遍历

for( j=g->vexnum-1;j>=0;j--){ //行数遍历

//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，

//加上g->matrix[j][i]的路径就是当前a[i]的路径

if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){

max=g->matrix[i][j]+b[j];

b[i]=max;

}

}

max=0;

}

//显示最长路径

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("V%d ",i+1);

}

printf(" ");

for(i=0;i<g->vexnum;i++){

printf("%d ",b[i]);

}

printf(" ");

printf("关键路径: ");

for(i=0;i<g->vexnum;i++){

if(a[i]==a[g->vexnum-1]-b[i]){

printf("V%c ",g->vexs[i]);

}

}

printf(" ");

}

void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){

// 输出最短距离并打印最短路径

int i = 0, pre, inverse_path[g->vexnum];

char s1[3],s2[3];

sprintf(s1, "V%d", (start+1));

sprintf(s2, "V%d", (end+1));

printf("从%s顶点到%s顶点的最短距离: %d ", s1, s2, distance[end]);

inverse_path[i] = end;

pre = path[end];

if(pre == -1){

printf("没有通路! ");

}else{

while(pre != start){

inverse_path[++i] = pre;

pre = path[pre];

}

inverse_path[++i] = start;

printf("从%s顶点到%s顶点的最短路径: ", s1, s2);

for(; i > 0; i--){

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s -> ", s1);

}

sprintf(s1, "V%d", (inverse_path[i]+1));

printf("%s ", s1);

}

return;

}

void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数

int distance[g->vexnum]; // 用于存放起始点到其余各点的最短距离

int path[g->vexnum]; // 用于存放起始点到其余各点最短路径的前一个顶点

int used[g->vexnum] = { 0 }; // 用于标记该顶点是否已经找到最短路径

int i, j, min_node, min_dis, pass_flag = 0;

for(i = 0; i < g->vexnum; i++){

distance[i] = g->matrix[start][i]; // 初始化距离数组

if(g->matrix[start][i] < INF){

path[i] = start; // 初始化路径数组

}else{

path[i] = -1;

}

}

used[start] = 1;

path[start] = start;

for(i = 0; i < g->vexnum; i++){

min_dis = INF;

for(j = 0; j < g->vexnum; j++){

if(used[j] == 0 && distance[j] < min_dis){

min_node = j;

min_dis = distance[j];

pass_flag++; // 标记是否存在通路

}

}

if(pass_flag != 0){

used[min_node] = 1;

for(j = 0; j < g->vexnum; j++){

if(used[j] == 0){

if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){

distance[j] = distance[min_node] + g->matrix[min_node][j];

path[j] = min_node;

}

}

}

}

}

print_shortest_path(g,distance, path, used, start, end);

return;

}

int main(){

int i,j;

PGraph gp;

char a[]={'1', '2', '3', '4', '5', '6', '7'};

int b[][3]={{'1', '2',3},

{'1', '3',2},

{'1', '4',6},

{'2', '4',2},

{'2', '5',4},

{'3', '4',1},

{'3', '6',3},

{'4', '5',1},

{'5', '7',3},

{'6', '7',4}};

int n=nLENGTH(a);

int e=eLENGTH(b);

gp=create_graph(b,a,n,e);

//打印邻接矩阵

printf("邻接矩阵: ");

for (i = 0; i < gp->vexnum; i++){

for (j = 0; j < gp->vexnum; j++)

printf("%d ", gp->matrix[j][i]);

printf(" ");

}

CPM_road(gp);

printf(" ");

for(i=0;i<gp->vexnum;i++){

for(j=0;j<gp->vexnum;j++){

if(i!=j)

shortest_path(gp,i, j);

}

}

return 0;

}

运行结果

❹ JAVA求10个景点间各个景点的最短路径 图随便话 距离随便 求代码

最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理罩源解。

public Stack findPath(Vertex 起始景点, Vertex 目标景点){
Queue <Vertex> q = new Queue<Vertex>();
s.enqueue(起始景点);
Vertex 当前位置;
while(!s.isEmpty()){
当前位置 = s.dequeue();
if (当前位置 == 目标景点) break;
for (每一个相邻于 当前位置 的景点 Vertex v){
if (!v.visited){
v.parent = 当前位置;
// 不是规定，不过可以节省一点时间
if (v == 目标景点){
current = v;
break;
}
s.enqueue(Vertex v);
v.visited = true;
}
}
}

Stack <Vertex> solution = new Stack <Vertex>();
Vertex parent = current;
while (parent != 起始景点){
solution.push(parent);
parent = current.parent;
}

for (graph中的每一个vertex) vertex.visited = false;

return solution(); // 其实这里建议用一个 Path 的inner class 来装所获得的路线
}

然后再 main 求每两个景点之间的距离即可
public static void main(String[] argv){
PathFinder pf = new PathFinder();

Stack[][] 路径 = new Stack[10][10];

for(int i=0; i<pf.vertices.length; i++){
for(int j=i+1; j<pf.vertices.length; j++){
Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);
路径[i][j] = s; 路虚咐径[j][i] = s; // 假设你的graph是一个undirected graph

}

}

// 这么一来就大功告成了！对于每两个景点n 与 m之间的最短路径就是在 stack[n][m] 中

}

还有一种方法就物誉态是用Depth First Search递归式的寻找路径，不过这样比较慢，而且我的代码可能会造成stack overflow

public Stack dfs(Vertex 当前景点，Vertex 目标景点){
if(当前景点 == 目标景点) return;

Stack solution = new Stack();
Stack temp;
for (相邻于 点钱景点 的每一个 Vertex v){
if (!v.visited){
v.visited = true;
temp = dfs(v, 目标景点);
// 抱歉，不记得是stack.size()还是stack.length()

if (solution.size() == 0) solution = temp;
else if(temp.size() < solution.size()) solution = temp;

v.visited = false; 复原

}

}

return solution;

}
然后再在上述的Main中叫dfs...

参考：
http://www.cs.berkeley.e/~jrs/61b/lec/29
http://www.cs.berkeley.e/~jrs/61b/lec/28

❺ 用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，并写出执行算法过程中各步的状态。

迪克斯加（Dijkstra）算没亩法(最短路径算法)是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中任意两个顶点之间的最短路径问题。
举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 迪科斯彻算法可以用来找到两个城市之间的最短路径。
迪科斯彻算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花含轿费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到u的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这谈察肆个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找权值最小的点为node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各点的权值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.

❻ java 计算多个点间的最短距离分配吗

java 计算多个点间的最短距离分配吗

package ; import java.awt.Point; public class JuLi { public static void main(String[] args) { Point p1 = new Point(5, 5); 定义第一个点的坐标(5,5),或者你自己设置x,y坐标 Point p2 = new Point(6,6); 定义第一个点的坐标(5,5),

求直线间的最短距离

利用二元函数求极值，先变成参数方程
x=t.....1)
y=2t....2)
z=t+1...3)
x=p.....4)
y=p+7...5)
z=p.....6)
得到：d=|(p-t)^2+(p+7-2t)^2+(p-t-1)^2|
dt=0,dp=0
2p-2t-2p+14-4t+2p-2t-2=0
-2p+2t-4p-28+8t-2p+2t+2=0
12p-16t+24=0
12p-18t+39=0
t=15/2,p=8
d=|1/4+0+1/4|=1/2

地球表面两点间最短距离怎么计算

球面两点最短距离是过这两点的大圆（半径等于球体的半径）的劣弧.
已知两地的
分别为σ1、σ2,纬度分别为φ1、φ2,求两地最近距离的公式为：
S=2πRθ/360° （1）
其中θ可由下面的式子求得：
[sin(θ/2)]^2=[sin(φ1-φ2)/2]^2+[sin(σ2-σ1)/2]^2cosφ1cosφ2 （2）
注：1、式中S为球面上任意两点的最短距离（球面距离）；
2、θ为两点间的
,在运用（2）式求θ时,纬度φ和
σ本身有
,通常北纬正,南纬负；东经正,西经负.
3、因不会用上下标,所以式中^2指平方； cosφ1cosφ2、σ2-σ1 、φ1-φ2中的1和和2为下标.
至于定性描述球面上两点的最短路线,可总结如盯昌下：
1、若两点在同一经线圈上或同在赤道上（从理论上讲,它们都是大圆）,则两地的最短路线是沿经线圈或赤道走劣弧.
2、若在同一
上（赤道除外）,两地最短路线是均向高纬弯曲（这两点所在的大圆劣弧）.
3、若两点既不在同一经线圈,也不在同一
圈,就较为复杂,一般不考虑了.

如何计算：地球上两点间最短距离

球面上两点闷最短距离是过两点和球心的圆上的劣弧。地球上也应类似。

地理中最短距离怎么计算

这种题目只能用勾股定理来做，当然做出来是个估算值，近似值，可用作参考。 你出的这个题目最多会出现在选择题中，并且选项数值一般差别较大。

数学 两点间最短距离

两点之间直线最短，所以要绕过障碍物，显然是连接端点的直线最短

怎么计算定点到抛物线的最短距离

称该点为A，抛物线上的点为B，过B的切线与AB垂直。这样可以求出B，以及AB

地球上面两点之间的最短距离怎么算，我

设立空间坐标换算
地球中心为原点,
北极为Y+,（0,0）度经纬为X+,东半球为Z+
然后比如说知道两点的经纬度
比如说东经a度北纬b度
然后换算成空间的坐标就是
（cosa*co *** ,sinb,sinaco *** ）
然后你就有(x1,y1,z1)和(x2,y2,z2)
然后用空间线段距离和余弦定理算出两点的夹角
然后已知一周角所对的弧就是4万千米
所以用那个角的大小除以一周角再成4万千米
就得到两点间的球面距离了
这个在弊困环球航行里面经常用到,很简单的.
地球的椭圆离心率不超过1%,一般情况下就没有必要换算成椭圆计算.
而且你问的也很奇怪,什么叫做长短轴?
空间里面的椭圆球是三维的,轴长是三个,X,Y,Z
如果要计算的话,我的计算方法也一样适用,不过步骤麻烦一点
1.先进行三维空间变换,把三轴不同的长度变成相同的长度凯卜扒,
求出新空间的坐标
2.反变换求出原空间的坐标和投影坐标以及夹角
3.椭圆球的切面也会是椭圆,求出那个椭圆的方程和它的投影方程
4.代入投影坐标求出原坐标的对应弧
5.用微积分求出对应弧长
然后就是需要的结果了.

问同一纬度的两点的最短距离，如何计算

北半球向北偏，南半球向南偏。
赤道上就是赤道纬线的距离

一个点到圆的最短距离为2最长距离为8，求半径

5

❼ 用java怎么用迪杰斯特拉算有向图有权值的最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}

MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封装路径距离
Map<String,String> pathInfo=new HashMap<String,String>();//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}

Main用于测试Dijkstra对象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}

❽ 谁知道用java编写计算平面内两条线段的最短距离，求解啊，急急急急急急急急啊~！！！十万火急啊~！！！！

求他们的4个端点坐标的距离。
假设:
线段一的2端坐标唯举亮是(10,10)(20,25)
线段二的2端坐标是(39,40)(60,60)
现判断是否相交。相交的话最短距离是0。
不是相交的话。计算2个线段的端点距离。答猜
端点距离可能有一下四种组合：
线段一(10,10)和线段二的(39,40)的距离
线段一(10,10)和线段二的(60,60)的距离
线段一(20,25)和线段二的(39,40)的指宽距离
线段一(20,25)和线段二的(60,60)的距离
求2点之间的距离就不用我说了吧。求出以上4个距离值。最小的那个就是最短距离

❾ 用java求最短路径问题，求源程序

import java.util.Vector;
public class Link {
private Vector link = new Vector();
// private Link next = null;
public Link() {
}

public boolean addNode(Node setNode){//增加一个节点
setNode = checkNode(setNode);
if(setNode != null){
this.link.addElement((Node)setNode);
return true;
}
return false;
}

public void delNode(Node setNode){ //删除一个节点
if(!this.link.isEmpty()){
for(int i=0;i < this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
this.link.remove(i);
//System.out.println("asdfasdfas:"+this.link.size());
break;
}
}
}
}

public Node checkNode(Node setNode){//判断节点是否在链表里面并取得两者的最佳值
if(!this.link.isEmpty() && setNode!=null){
for(int i=0;i < this.link.size(); i++)
{
if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){
if(setNode.getStep() < ((Node)this.link.elementAt(i)).getStep()){
setNode = (Node)this.link.elementAt(i);
this.link.remove(i);
}
else
return null;
break;
}
}
}
return setNode;
}

public boolean isEmpty(){
return this.link.isEmpty();
}

public Node getBestNode(){ //得到最好的节点
Node tmpNode = null;
if(!this.link.isEmpty()){
tmpNode = (Node)this.link.elementAt(0);
//System.out.println("tmpNodeStep:"+tmpNode.getStep());
//System.out.print("OpenNode(pos,step):");
for(int i=1;i < this.link.size(); i++)
{
//System.out.print("("+((Node)this.link.elementAt(i)).getPos()+","+((Node)this.link.elementAt(i)).getStep()+")");
if(tmpNode.getJudgeNum() >= ((Node)this.link.elementAt(i)).getJudgeNum()){
tmpNode = (Node)this.link.elementAt(i);
}
}
}
return tmpNode;
}

}

public class FindBestPath {
private char[][] map = null;//地图
private int maxX,maxY;//最大的地图边界大小
Node startNode = null;//入口
Node endNode = null;//出口
private int endX,endY;
/*初始化
*@param setMap 地图
*@param setX,setY 边界值
//////////*@param startNode 入口
//////////*param endNode 出口
*@param sX,sY:开始点
*@param eX,eY:结束点
*/
public FindBestPath(char[][] setMap,int setX,int setY,int sX,int sY,int eX,int eY) {
this.map = setMap;
this.maxY = setX - 1; //x,y互换
this.maxX = setY - 1; //x,y互换
//this.startNode = sNode;
//this.endNode = eNode;

Node sNode = new Node();
Node eNode = new Node();

sNode.setFarther(null);
sNode.setPos(posToNum(sX,sY));
sNode.setStep(0);
eNode.setPos(posToNum(eX,eY));

this.startNode = sNode;
this.endNode = eNode;

this.endX = eX;//numToX(eNode.getPos());
this.endY = eY;//numToY(eNode.getPos());

}

public int posToNum(int x,int y){//从xy坐标获得编号
return (x+y*(this.maxY+1));
}

public int numToX(int num){//从编号获得x坐标
return (num%(this.maxY+1));
}

public int numToY(int num){//从编号获得y坐标
return (int)(num/(this.maxY+1));
}

public boolean checkVal(int x,int y){//判断是否为障碍
//System.out.println("map["+x+"]["+y+"]="+map[x][y]);
if(this.map[x][y] == 'N')
return false;
else
return true;
}

public int judge(Node nowNode){//一定要比实际距离小
//System.out.println("nowNodePos:"+nowNode.getPos());
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
int distance = Math.abs((nowX-this.endX))+Math.abs((nowY-this.endY));
// System.out.println("distance:"+distance);
return distance;
}

public Node getLeft(Node nowNode){//取得左节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY > 0){//判断节点是否到最左
if(checkVal(nowX,nowY-1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY-1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}

public Node getRight(Node nowNode){//取得右节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowY < this.maxX){//判断节点是否到最左
if(checkVal(nowX,nowY+1)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX,nowY+1));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}

public Node getTop(Node nowNode){//取得上节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX > 0){//判断节点是否到最左
if(checkVal(nowX-1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX-1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}

public Node getBottom(Node nowNode){//取得下节点
int nowX = numToX(nowNode.getPos());
int nowY = numToY(nowNode.getPos());
Node tmpNode = new Node();
if(nowX < this.maxY){//判断节点是否到最左
if(checkVal(nowX+1,nowY)){
tmpNode.setFarther(nowNode);
tmpNode.setPos(posToNum(nowX+1,nowY));
tmpNode.setStep(nowNode.getStep()+1);
tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
return tmpNode;
}
}
return null;
}

public Link getBestPath(){//寻找路径
Link openLink = new Link();//没有访问的路径
Link closeLink = new Link();//访问过的路径
Link path = null;//最短路径
Node bestNode = null;

Node tmpNode = null;

openLink.addNode(this.startNode);
while(!openLink.isEmpty())//openLink is not null
{
bestNode = openLink.getBestNode();//取得最好的节点
//System.out.println("bestNode:("+numToX(bestNode.getPos())+","+numToY(bestNode.getPos())+")step:"+bestNode.getJudgeNum());
if(bestNode.getPos()==this.endNode.getPos())
{
/*this.endNode.setStep(bestNode.getStep()+1);
this.endNode.setFarther(bestNode);
this.endNode.setJudgeNum(bestNode.getStep()+1);*/
path = makePath(bestNode);
break;
}
else
{
tmpNode = closeLink.checkNode(getLeft(bestNode));
if(tmpNode != null)
//System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getRight(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getTop(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getBottom(bestNode));
if(tmpNode != null)
// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
openLink.addNode(tmpNode);

openLink.delNode(bestNode);
closeLink.addNode(bestNode);
}
}
return path;
}

public Link makePath(Node lastNode){//制造路径
Link tmpLink = new Link();
Node tmpNode = new Node();
int x,y;
tmpNode = lastNode;
if(tmpNode != null){
do{
x=numToX(tmpNode.getPos());
y=numToY(tmpNode.getPos());
System.out.println("map["+x+"]["+y+"]="+map[x][y]);
tmpLink.addNode(tmpNode);
tmpNode = tmpNode.getFarther();
}while(tmpNode != null);
}else
{
System.out.println("Couldn't find the path!");
}
return tmpLink;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
char[][] map ={
{'Y', 'N', 'z', 'y', 'x', 'w', 'v', 'N', 'N', 'N'},
{'Y', 'N', '1', 'N', 'N', 'N', 'u', 't', 'N', 'N'},
{'N', '1', '2', '1', '1', '1', 'N', 's', 'N', 'N'},
{'N', 'N', '1', 'N', '9', 'N', 'q', 'r', 'N', 'N'},
{'N', 'N', '1', 'N', 'n', 'o', 'p', 'N', 'N', 'N'},
{'N', '4', '5', '6', 'm', 'N', 'N', 'N', 'N', 'N'},
{'N', '3', 'N', '5', 'l', 'k', 'j', 'N', 'N', 'N'},
{'N', 'N', '3', '4', 'N', 'd', 'i', 'd', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'h', 'N', 'N', 'N'},
{'N', '1', 'N', 'N', '1', 'N', 'g', 'N', 'N', 'N'},
{'N', 'a', 'b', 'c', 'd', 'e', 'f', 'N', 'N', 'N'}
};
/*map[x][y]
*如上所示：maxY=10 maxX=11 横的代表maxY,竖的代表maxX 可以自己替换
*地图的读取是
*for(i=1;i<行的最大值;i++)
* for(j=1;j<列的最大值;j++)
* map[i][j] = 地图[i][j]
*/
Link bestPath = new Link();
/*startNode.setFarther(null);
startNode.setPos(21);
startNode.setStep(0);

//endNode.setFarther(startNode);
endNode.setPos(79);
//endNode.setStep(0);*/

FindBestPath path = new FindBestPath(map, 11, 10, 10, 1, 0, 2);
//FindBestPath path = new FindBestPath(map, 11, 10, startNode, endNode);

bestPath = path.getBestPath();
//bestPath.printLink();

}

}

public class Node {
private int step;//从入口到该节点经历的步数
private int pos;//位置
private Node farther;//上一个结点
private int judgeNum;
public Node() {
}
public void setStep(int setStep){
this.step = setStep;
}
public int getStep(){
return this.step;
}
public void setPos(int setPos){
this.pos = setPos;
}
public int getPos(){
return this.pos;
}
public void setFarther(Node setNode){
this.farther = setNode;;
}
public Node getFarther(){
return this.farther;
}
public void setJudgeNum (int setInt){
this.judgeNum = setInt;;
}
public int getJudgeNum(){
return this.judgeNum;
}
}