最短路径算法怎么做（最短路径算法做图像分割的代码-）

大家好！今天让创意岭的小编来大家介绍下关于最短路径算法怎么做的问题，以下是小编对此问题的归纳整理，让我们一起来看看吧。

开始之前先推荐一个非常厉害的Ai人工智能工具，一键生成原创文章、方案、文案、工作计划、工作报告、论文、代码、作文、做题和对话答疑等等

只需要输入关键词，就能返回你想要的内容，越精准，写出的就越详细，有微信小程序端、在线网页版、PC客户端

官网：https://ai.de1919.com。

创意岭作为行业内优秀的企业，服务客户遍布全球各地，如需了解SEO相关业务请拨打电话175-8598-2043，或添加微信：1454722008

本文目录:

• 1、java 最短路径算法 如何实现有向 任意两点的最短路径

• 2、求写最短路径算法。由A地到E地，途经B（B1，B2，B3）C（C1，C2，C3）地，基于矩阵乘法求最短路径。给出步骤

• 3、求一个最短路径的算法

• 4、最短路径（Dijkstra算法）

一、java 最短路径算法 如何实现有向 任意两点的最短路径

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

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：

1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点

2.初始阶段，将初始节点放入close，其他所有节点放入open

3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：

Node对象用于封装节点信息，包括名字和子节点

[java] view plain copy

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 copy

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 copy

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 copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

}

二、求写最短路径算法。由A地到E地，途经B（B1，B2，B3）C（C1，C2，C3）地，基于矩阵乘法求最短路径。给出步骤

们把求A →E 的最短路分解为四个阶段A →B →C→D →E 来求解。每一个阶段可以用一个矩阵来表示，这个矩阵称为权矩阵。相邻阶段的路径可以用权矩阵的乘积来表示。但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大. 如果是求极大,改为取大运算,此时如果不同层节点间没有连接，则视它们的距离为0。

如下：

由A地到B地的距离可表示为：A[2 5 8]

由B地到C地的权矩阵可表示为

[3，6，5；7，10，8；4，9，6]

因此由A到C的权矩阵为[2，5，8][3，6，5；7，10，8；4，9，6]＝[5，8，7]

因此由A到D的权矩阵为[5，8，7)][7，5；3，4；5，2]＝[11 ，9]

由A→E的权矩阵为：[11 ，9][4，2)]=[15,11]

因此从家里到学校的最短距离为11百米，最近的路径为从A地出发经过B1地C1地D2地到达E地。

下面我们给出基于“矩阵乘法”求解最短路的算法:

第一阶段:计算出图中从起始点到终点最短路的长度.

step1 　划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;

step2 　依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 , …, N21) ; (若第i 层有m 个顶点;第i + 1 层有n

个顶点, 则从第i 层到第i + 1 层的权矩阵为m *n

阶) .

step3 　按照我们定义的矩阵乘法计算出最短路的

数值.

第二阶段:寻找最短路所经过的中间点.

(利用第一阶段中step2 的数据) 计算出从第i 层到

终点的最短路, 对比与i21 层到终点的最短路, 从而确

定出第i 层上最短路所经过的顶点( i = 2 , …, N21) .

三、求一个最短路径的算法

以前看到过，贴给你

Private Function OrderXY(X() As Double, Y() As Double)

Dim i, j, k, m, n, num, temp As Double

Dim NewX() As Double

Dim NewY() As Double

Dim Smin As Double '定义最短总距离

If UBound(X()) <> UBound(Y()) Then MsgBox "坐标错误": Exit Function '防止数据错误

n = UBound(X())

ReDim p(n) As Long

p(0) = 0: num = 1

For i = 1 To n

p(i) = i 'p()数组依次存储从0到n共n+1个数

num = num * i '计算num，num表示的是n个坐标（除X(0),Y(0)以外)共有n！种排列

Next

ReDim Stance(num - 1) As Double '定义数组存储每种连接方法的总距离

ReDim NewX(n)

ReDim NewY(n)

For i = 0 To n - 1 'Stance（0）是按照原坐标顺序依次连接的总距离

Stance(0) = Stance(0) + Sqr((Y(i + 1) - Y(i)) * (Y(i + 1) - Y(i)) + (X(i + 1) - X(i)) * (X(i + 1) - X(i)))

Next

Smin = Stance(0)

For k = 0 To n

NewX(k) = X(k)

NewY(k) = Y(k)

Next

i = n - 1

'下面对p()数组的n个数（除0以外）进行排列，每产生一种排列方式，坐标数组的数据就对应交换，并计算这一路径的总距离

Do While i > 0

If p(i) < p(i + 1) Then

For j = n To i + 1 Step -1 '从排列右端开始

If p(i) <= p(j) Then Exit For '找出递减子序列

Next

temp = p(i): p(i) = p(j): p(j) = temp '将递减子序列前的数字与序列中比它大的第一个数交换

temp = X(i): X(i) = X(j): X(j) = temp '与之对应的X Y也交换

temp = Y(i): Y(i) = Y(j): Y(j) = temp

For j = n To 1 Step -1 '将这部分排列倒转

i = i + 1

If i >= j Then Exit For

temp = p(i): p(i) = p(j): p(j) = temp

temp = X(i): X(i) = X(j): X(j) = temp

temp = Y(i): Y(i) = Y(j): Y(j) = temp

Next

m = m + 1

For k = 0 To n - 1

Stance(m) = Stance(m) + Sqr((Y(k + 1) - Y(k)) * (Y(k + 1) - Y(k)) + (X(k + 1) - X(k)) * (X(k + 1) - X(k)))

Next

If Stance(m) <= Smin Then

Smin = Stance(m)

For k = 0 To n

NewX(k) = X(k): NewY(k) = Y(k)

Next

End If

i = n

End If

i = i - 1

Loop

For k = 0 To n

X(k) = NewX(k): Y(k) = NewY(k)

Next '此时的X（） Y（） 就按照最短路径排列

End Function

四、最短路径（Dijkstra算法）

0<-->2 = 667;

0<-->5 = 689;

0<-->9 = 1160;

0<-->13 = 1046;

1<-->13 = 242;

2<-->3 = 3036;

3<-->11 = 1892;

4<-->8 = 1180;

4<-->9 = 303;

4<-->14 = 825;

5<-->6 = 898;

5<-->9 = 695;

5<-->10 = 511;

6<-->7 = 707;

6<-->12 = 1419;

6<-->14 = 482;

7<-->8 = 1588;

10<-->11 = 676;

10<-->12 = 1346;

不是已经有答案了吗?还问什么呢

以上就是关于最短路径算法怎么做相关问题的回答。希望能帮到你，如有更多相关问题，您也可以联系我们的客服进行咨询，客服也会为您讲解更多精彩的知识和内容。

推荐阅读：

图的四种最短路径算法（图的四种最短路径算法是）

院线电影最短时长

最短路径算法有哪些（最短路径算法总结）

制造业包括哪些行业（高端制造业包括哪些行业）

海报设计app（手机制作海报的app免费）