package testShortPath;
public class Vertex {
public char label;
public boolean isVisited;
public Vertex(char label) {
this.label = label;
}
}
package testShortPath;
import java.util.LinkedList;
import java.util.List;
public class ShortDistAndPath {
public int distance;
public List<Integer> pathList = new LinkedList<Integer>();
public ShortDistAndPath(int distance) {
this.distance = distance;
}
}
package testShortPath;
public class Graph {
/**最大的顶点数目*/
private final int MAX_VERTS = 20;
/**无穷大*/
private final int INFINITY = 1000000;
/**顶点列表*/
private Vertex[] vertexList;
/**邻接矩阵*/
private int[][] adjMat;
/**顶点数目*/
private int vertNum;
/**访问过的顶点数目*/
private int visitedVertNum;
/**最短路径以及路径的数组*/
private ShortDistAndPath[] shortDistAndPathStrs;
/**当前的顶点*/
private int currentVert;
/**指定顶点距当前顶点的距离*/
private int startToCurrentDist;
public Graph() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
vertNum = 0;
visitedVertNum = 0;
for(int j=0;j<MAX_VERTS;j++) {
for(int k = 0;k < MAX_VERTS;k++) {
adjMat[j][k] = INFINITY;
}
}
shortDistAndPathStrs = new ShortDistAndPath[MAX_VERTS];
}
public void addVertex(char lab){
vertexList[vertNum ++] = new Vertex(lab);
}
public void addEdge(int start,int end,int weight) {
adjMat[start][end] = weight;
}
/**
* 算法的核心
*/
public void path() {
int startTree = 0;
vertexList[startTree].isVisited = true;
visitedVertNum = 1;
for(int i=0;i<vertNum;i++) {
shortDistAndPathStrs[i] = new ShortDistAndPath(adjMat[startTree][i]);
shortDistAndPathStrs[i].pathList.add(startTree);//初始化每个路径
shortDistAndPathStrs[i].pathList.add(i);
}
while (visitedVertNum < vertNum) {
int minIndex = getMin();
int minDist = shortDistAndPathStrs[minIndex].distance;
if(minDist == INFINITY) {
System.out.println("There are unreachable vertices.");
break;
} else {
currentVert = minIndex;
startToCurrentDist = minDist;
}
vertexList[currentVert].isVisited = true;
visitedVertNum ++;
adjust_sPath();
}
displayPaths();
}
/**
* 得到未访问的，最短路径的顶点的下标
* @return
*/
public int getMin() {
int minDist = INFINITY;
int minIndex = 0;
for(int i=0;i<vertNum;i++) {
if(!vertexList[i].isVisited && shortDistAndPathStrs[i].distance < minDist) {
minDist = shortDistAndPathStrs[i].distance;
minIndex = i;
}
}
return minIndex;
}
public void adjust_sPath() {
int vertIndex = 1;
while(vertIndex < vertNum) {
if(vertexList[vertIndex].isVisited) {
vertIndex ++;
continue;
}
int specificToNext = startToCurrentDist + adjMat[currentVert][vertIndex];
int shortDist = shortDistAndPathStrs[vertIndex].distance;
if(shortDist > specificToNext) {
shortDistAndPathStrs[vertIndex].distance = specificToNext;
shortDistAndPathStrs[vertIndex].pathList.clear();//更新路径
shortDistAndPathStrs[vertIndex].pathList.addAll(shortDistAndPathStrs[currentVert].pathList);
shortDistAndPathStrs[vertIndex].pathList.add(vertIndex);
}
vertIndex ++;
}
}
public void displayPaths() {
for(int j=0;j<vertNum;j++) {
for(int g=0;g<shortDistAndPathStrs[j].pathList.size();g++) {
System.out.print(vertexList[shortDistAndPathStrs[j].pathList.get(g)].label);
if(g != shortDistAndPathStrs[j].pathList.size() -1) {
System.out.print("-->");
}else {
System.out.print(" =");
if(shortDistAndPathStrs[j].distance == INFINITY) {
System.out.print("inf");
} else {
System.out.print(shortDistAndPathStrs[j].distance);
}
}
}
System.out.println();
}
}
/**
* Test
* @param args
*/
public static void main(String[] args) {
Graph theGraph = new Graph();
theGraph.addVertex('A');//0
theGraph.addVertex('B');//1
theGraph.addVertex('C');//2
theGraph.addVertex('D');//3
theGraph.addVertex('E');//4
theGraph.addEdge(0, 1, 50);
theGraph.addEdge(0, 3, 80);
theGraph.addEdge(1, 2, 60);
theGraph.addEdge(1, 3, 90);
theGraph.addEdge(2, 4, 40);
theGraph.addEdge(3, 2, 20);
theGraph.addEdge(3, 4, 70);
theGraph.addEdge(4, 1, 50);
theGraph.path();
System.out.println();
}
}
package testShortPath;
public class Graph {
/**最大的顶点数目*/
private final int MAX_VERTS = 20;
/**无穷大*/
private final int INFINITY = 1000000;
/**顶点列表*/
private Vertex[] vertexList;
/**邻接矩阵*/
private int[][] adjMat;
/**顶点数目*/
private int vertNum;
/**访问过的顶点数目*/
private int visitedVertNum;
/**最短路径以及路径的数组*/
private ShortDistAndPath[] shortDistAndPathStrs;
/**当前的顶点*/
private int currentVert;
/**指定顶点距当前顶点的距离*/
private int startToCurrentDist;
public Graph() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
vertNum = 0;
visitedVertNum = 0;
for(int j=0;j<MAX_VERTS;j++) {
for(int k = 0;k < MAX_VERTS;k++) {
adjMat[j][k] = INFINITY;
}
}
shortDistAndPathStrs = new ShortDistAndPath[MAX_VERTS];
}
public void addVertex(char lab){
vertexList[vertNum ++] = new Vertex(lab);
}
public void addEdge(int start,int end,int weight) {
adjMat[start][end] = weight;
}
/**
* 算法的核心
*/
public void path() {
int startTree = 0;
vertexList[startTree].isVisited = true;
visitedVertNum = 1;
for(int i=0;i<vertNum;i++) {
shortDistAndPathStrs[i] = new ShortDistAndPath(adjMat[startTree][i]);
shortDistAndPathStrs[i].pathList.add(startTree);//初始化每个路径
shortDistAndPathStrs[i].pathList.add(i);
}
while (visitedVertNum < vertNum) {
int minIndex = getMin();
int minDist = shortDistAndPathStrs[minIndex].distance;
if(minDist == INFINITY) {
System.out.println("There are unreachable vertices.");
break;
} else {
currentVert = minIndex;
startToCurrentDist = minDist;
}
vertexList[currentVert].isVisited = true;
visitedVertNum ++;
adjust_sPath();
}
displayPaths();
}
/**
* 得到未访问的，最短路径的顶点的下标
* @return
*/
public int getMin() {
int minDist = INFINITY;
int minIndex = 0;
for(int i=0;i<vertNum;i++) {
if(!vertexList[i].isVisited && shortDistAndPathStrs[i].distance < minDist) {
minDist = shortDistAndPathStrs[i].distance;
minIndex = i;
}
}
return minIndex;
}
public void adjust_sPath() {
int vertIndex = 1;
while(vertIndex < vertNum) {
if(vertexList[vertIndex].isVisited) {
vertIndex ++;
continue;
}
int specificToNext = startToCurrentDist + adjMat[currentVert][vertIndex];
int shortDist = shortDistAndPathStrs[vertIndex].distance;
if(shortDist > specificToNext) {
shortDistAndPathStrs[vertIndex].distance = specificToNext;
shortDistAndPathStrs[vertIndex].pathList.clear();//更新路径
shortDistAndPathStrs[vertIndex].pathList.addAll(shortDistAndPathStrs[currentVert].pathList);
shortDistAndPathStrs[vertIndex].pathList.add(vertIndex);
}
vertIndex ++;
}
}
public void displayPaths() {
for(int j=0;j<vertNum;j++) {
for(int g=0;g<shortDistAndPathStrs[j].pathList.size();g++) {
System.out.print(vertexList[shortDistAndPathStrs[j].pathList.get(g)].label);
if(g != shortDistAndPathStrs[j].pathList.size() -1) {
System.out.print("-->");
}else {
System.out.print(" =");
if(shortDistAndPathStrs[j].distance == INFINITY) {
System.out.print("inf");
} else {
System.out.print(shortDistAndPathStrs[j].distance);
}
}
}
System.out.println();
}
}
/**
* Test
* @param args
*/
public static void main(String[] args) {
Graph theGraph = new Graph();
theGraph.addVertex('A');//0
theGraph.addVertex('B');//1
theGraph.addVertex('C');//2
theGraph.addVertex('D');//3
theGraph.addVertex('E');//4
theGraph.addEdge(0, 1, 50);
theGraph.addEdge(0, 3, 80);
theGraph.addEdge(1, 2, 60);
theGraph.addEdge(1, 3, 90);
theGraph.addEdge(2, 4, 40);
theGraph.addEdge(3, 2, 20);
theGraph.addEdge(3, 4, 70);
theGraph.addEdge(4, 1, 50);
theGraph.path();
System.out.println();
}
}
execute Result:
A-->A =inf
A-->B =50
A-->D-->C =100
A-->D =80
A-->D-->C-->E =140
分享到：
相关推荐
用贪心算法解单源最短路径问题 在计算机科学和信息技术领域中，单源最短路径问题是指从一个源点到其他顶点的最短路径问题。它是一种典型的图论问题，广泛应用于交通网络、通信网络、计算机网络等领域。贪心算法是...
在计算机科学领域，特别是在图论和网络分析中，"最短路径问题"是一个经典的问题，旨在找到连接两个节点间路径的最小成本或时间。而"第二最短路径问题"则是其扩展，它不仅要求找到最短路径，还要找出次优的路径，即第...
最短路径选择问题在计算机科学和网络优化领域中是一个经典问题，主要目的是在给定的图中找到从源节点到目标节点的最短路径。KSP（K Shortest Paths）算法则是寻找图中的前K条最短路径。本文将详细讨论戴维编译的K条...
描述提到“floyd计算最短路径，只需要更改邻接矩阵”，意味着该算法通过迭代更新邻接矩阵来找到最短路径。 **Floyd最短路径算法详解** Floyd-Warshall算法是一种动态规划方法，它通过逐步考虑所有可能的中间节点来...
最短路径问题是一个经典的问题，寻找无向图中的最短路径有着广泛的应用，比如路由选择、网络优化等。本项目以Java语言实现了求解无向图所有最短路径的算法。 1. **Dijkstra算法** Dijkstra算法是最常用的单源最短...
总结，通过ArcGIS for Android，我们可以轻松地实现在地图上展示多点之间的最短路径，并显示详细的路径信息。关键在于正确配置RouteParamet，执行路线查找，解析RouteResult，并在地图上进行图形化展示。记住，根据...
用 vi 到 vm 的最短路径和最短路径长度对 vi 到其它尚未求出最短路径的那些终点的当前最短路径及长度作必要地修改，使之成为当前新的最短路径和最短路径长度，当进行 n-2 次（因最多考虑 n-2 个中间点）后算法结束。...
- 输出显示：程序应清晰地显示最短路径及路径长度。 - 动态更新：当用户改变输入时，GUI应实时更新最短路径。 - 错误处理：处理无效输入或不存在的路径情况。 6. **数据结构**：为了存储图的信息，通常会使用...
数据结构课程设计中，"校园最短路径问题"是一个典型的图论问题，旨在解决如何从校园内一个指定的地点出发，找到到达其他任何地点的最短路径。这涉及到图的最短路径算法，如Dijkstra算法，以及图的存储结构，如邻接...
【校园最短路径问题的研究与实现】这篇课程设计主要探讨了如何解决在校园环境中寻找任意两点间最短路径的问题。该程序使用C++编程语言，借助Microsoft Visual C++ 6.0开发环境来实现。设计的目标是允许用户指定起点...
最短路径问题是图论中的一个经典问题，其基本概念涉及到有向图或无向图中，从某一顶点到另一顶点或多个顶点之间经过的路径总权值最小的路径。在图论中，路径上的权值可以是边的长度、时间或其他度量，而权值最小的...
在MATLAB中实现最短路径算法，通常会涉及到图论中的经典问题，如Dijkstra算法或Floyd-Warshall算法。这些算法广泛应用于网络优化、地理信息系统和物流规划等领域。以下将详细介绍这两种算法以及如何在MATLAB中进行...
6. **主函数**：描述中的“main”可能是指主函数，它调用`canshuo`并处理结果，显示从源节点到目标节点的最短路径和长度。 7. **文件结构**：虽然没有给出具体文件内容，但可以推测`canshuo.m`是核心算法实现，而...
它在解决复杂问题，如寻找最短路径问题时，展现出了强大的能力。在这个MATLAB程序中，我们将深入探讨如何利用遗传算法来求解最短路径问题。 在最短路径问题中，目标是找到在给定网络中从一个源节点到一个目标节点的...
Dijkstra算法是一种常用的图搜索算法，用于计算图中的一条最短路径。该算法的主要思想是从图的某个顶点出发，逐步扩展到其他顶点，直到找到目标顶点的最短路径。 在本节中，我们将详细讲述Dijkstra算法的实现过程，...
然而，A*算法并不直接支持找到k-最短路径，但可以通过修改来实现，例如每次找到一个最短路径后更新启发式函数。 4. Yen's算法：Yen算法是专门设计用来找k-最短路径的算法，基于Dijkstra算法。基本思路是，从起点...
最短路径分析主要解决的问题是在给定的图中寻找两个节点之间路径的最小成本。这在各种实际场景中都有应用，例如在地图应用中找到两点间的最快驾驶路线，或者在网络中找出数据传输的最低延迟路径。常见的最短路径算法...
在需求分析部分，问题被定义为寻找校园内的最短路径，这需要实现一系列功能，包括输出顶点信息、边的信息，修改边的长度，求最短路径，删除和插入边。其中，求最短路径的算法采用了Dijkstra算法，这是一种解决单源...