有向圖最短距離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;
}
}