最短路径Dijkstra算法(JAVA)

zz/2024/5/21 20:50:38

 

  

 

/*

 * Graph.java

 */

class Vertex {

     public char label;

     public boolean isInTree;

     public Vertex(char label) {

         this.label = label;

         isInTree = false;

     }

}

//sPath[]用来存储父节点和距离。

class DistPare {

     public int parentVertex;

     public int distance;

     public DistPare(int parentVertex, int distance) {

         this.parentVertex = parentVertex;

         this.distance = distance;

     }

}

public class Graph {

     private final int MAX_VERTEX = 20;

     private final int INFINITY = 999999;

     private int nVerts;

     private int nTree;

     private int currentVertex;

     private int startToCurrent;

     private int adjMatrix[][];

     private Vertex vertexList[];

     private DistPare sPath[];

    

     public Graph() {

         adjMatrix = new int[MAX_VERTEX][MAX_VERTEX];

         vertexList = new Vertex[MAX_VERTEX];

         sPath = new DistPare[MAX_VERTEX];

         nVerts = 0;

         nTree = 0;

         for(int i=0; i<MAX_VERTEX; i++)

              for(int j=0; j<MAX_VERTEX; j++)

                   adjMatrix[i][j] = INFINITY;

     }

     public void addVertex(char label) {

         vertexList[nVerts++] = new Vertex(label);

     }

     //有向图

     public void addOneEdge(int start, int end, int weight) {

         adjMatrix[start][end] = weight ;

     }

     public void dijkstra() {

         int startTree = 0;

         vertexList[startTree].isInTree = true;

         nTree = 1;

         for(int j=0; j<nVerts; j++) {

              int tempDist = adjMatrix[startTree][j];

              sPath[j] = new DistPare(startTree, tempDist);

         }

         while(nTree<nVerts) {

              int indexMin = getMin();

              int minDist = sPath[indexMin].distance;

              if(minDist == INFINITY) {

                   System.out.println("有无法到达的顶点");

              }

              else {

                   currentVertex = indexMin;

                   startToCurrent = sPath[indexMin].distance;

              }

              vertexList[currentVertex].isInTree = true;

              nTree ++;

              adjust_sPath();

         }

         displaypaths();

     }

    

     private void displaypaths() {

         for(int j=0; j<nVerts; j++) {

              System.out.print(vertexList[j].label + "=");

              if(sPath[j].distance == INFINITY)

                   System.out.print("inf");

              else

                   System.out.print(sPath[j].distance);

              char parent = vertexList[sPath[j].parentVertex].label;

              System.out.print("(" + parent + ") ");

         }

         System.out.println(" ");

     }

    

     private void adjust_sPath() {

         int column = 1;

         while(column < nVerts) {

              if(vertexList[column].isInTree) {

                   column ++;

                   continue;

              }

              int currentToFringe = adjMatrix[currentVertex][column];

              int startToFringe = startToCurrent + currentToFringe;

              int sPathDist = sPath[column].distance;

              if(startToFringe<sPathDist) {

                   sPath[column].parentVertex = currentVertex;

                   sPath[column].distance = startToFringe;

              }

              column ++;

         }

     }

    

     private int getMin() {

         int minDist = INFINITY;

         int indexMin = 0;

         for(int j=0; j<nVerts; j++) {

              if(!vertexList[j].isInTree && sPath[j].distance<minDist) {

                   minDist = sPath[j].distance;

                   indexMin = j;

              }

         }

         return indexMin;

     }

    

}

/*

 * Dijkstra.java

 */

public class Dijkstra {

     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.addOneEdge(0, 1, 50);//AB 50

         theGraph.addOneEdge(0, 3, 80);//AD 80

         theGraph.addOneEdge(1, 2, 60);//BC 60

         theGraph.addOneEdge(1, 3, 90);//BD 90

         theGraph.addOneEdge(2, 4, 40);//CE 40

         theGraph.addOneEdge(3, 2, 20);//DC 20

         theGraph.addOneEdge(3, 4, 70);//DE 70

         theGraph.addOneEdge(4, 1, 50);//EF 50

        

         System.out.println("Dijkstra: ");

         theGraph.dijkstra();

     }

 

}

 

 


http://www.ngui.cc/zz/2700343.html

相关文章

五台归来

五台之旅结束&#xff0c;学习之。 2009.5.27~2009.6.13作息时间表&#xff1a; 7&#xff1a;00起床 7&#xff1a;30~8&#xff1a;50图书馆&#xff1a;算法、数据结构、JAVA程序员宝典 9&#xff1a;00~12&#xff1a;00办公室&#xff1a;WSN 12&#xff1a;30~14&…

PL/SQL 调试存储过程(报错ora-01036 非法的变量名/编号)

存储过程&#xff1a; create or replace procedure zhanshi(v_pid article.pid%type) is cursor c is select * from article where pid v_pid;begin for v_article in c loop dbms_output.put_line(v_article.cont); if (v_article.isleaf 0) then zhansh…

Arduino+WZ指令+Onenet

title: ArduinoWZ指令Onenet tags: Onenet date: 2019-02-24 00:53:00 视频演示&#xff1a; src"//player.bilibili.com/player.html?aid44421747&cid77777406&page1" scrolling"yes" border"0" allowfullscreen"true"> …

一行代码完成485通讯与数据回传以及CRC校验

title: 一行代码完成485通讯与数据回传以及CRC校验 tags: STM32 date: 2019-03-16 21:10:00 由于工作需要&#xff0c;我对现有的485通讯方式进行了一个总结&#xff0c;同时也包含自己原创的一些算法来快速实现485通讯与CRC校验&#xff0c;以及返回值的处理 看下效果&#xf…

209年7月生活记录

title: 最近生活记录 tags: 生活 date: 2019-07-28 21:46:00 OK&#xff0c;今天来记录一下我的生活近况&#xff0c;其实这一段儿工作比较忙&#xff0c;尤其是最近在搞联通动环监控的B接口协议&#xff0c;相对来说还是很复杂的&#xff0c;但是做好以后的效果还是可以的&…

涂鸦NBIOT OpenCPU开发快速入门(三)

1、开发板选择 工欲善其事&#xff0c;必先利其器。 我之前做了两款开发板&#xff08;其实主要是为了我工作上开发的方便&#xff09;&#xff0c;第一款用来测试通用对接&#xff08;&#xff2e;&#xff22;&#xff0b;&#xff2d;&#xff23;&#xff35;&#xff09;…

Elasticsearch API查询

1. 查询索引中的全部数据 public class EsTest_Doc_Query {public static void main(String[] args) throws IOException {RestHighLevelClient client new RestHighLevelClient(RestClient.builder(new HttpHost("localhost", 9200, "http")));// 1.查询…

cocos2d cut the rope

http://www.cocoachina.com/downloads/video/2010/1103/2291.html

需要将一个11GB的文件传输到另外一台服务器,如何断点续传?如何限制带宽?

1、 http://www.redicecn.com/html/Linux/20130703/460.html 需要将一个11GB的文件传输到另外一台服务器&#xff0c;如何断点续传&#xff1f;如何限制带宽&#xff1f; 使用rsync&#xff0c;完整命令如下&#xff1a; rsync -av --bwlimit1000 --progress --inplace --rshss…
最新文章