首页 > 代码库 > Dijkstra算法
Dijkstra算法
Dijkstra算法又称单源点距离最短问题
设一个图中有V0,V1,V2,V3...等顶点，这里设求的是V0到V1,V2,...的最短距离
基本思想
V0到剩余顶点的直接距离dist[]（不经过其他任何节点，没有联通的设为无穷大）中,找出一个最小的，设其顶点为V1，这里我们就求出了V0到V1的最短距离。
将V0和V1划分到一个集合中（最短距离已经求出的顶点集合）S,用V0直接到Vx的距离与V0V1Vx的距离进行比较，如果后者小更新dist[]
一直重复下去，直到找出所有节点的最短距离
Ps:语文没学好，加上不太想画图之类的弄，仅仅记录一下
上代码吧
1 package com.gxf.graph; 2 3 /** 4 * @author xiangfei 5 * 6 */ 7 public class Graph { 8 //这里用邻接矩阵存储图 9 int cost[][] = new int[6][6];10 int max = 1000;11 int dist[] = new int[6];12 public Graph(){13 //初始化矩阵14 for(int i = 0; i < 6; i++){15 for(int j = 0; j < 6; j++){16 cost[i][j] = max;17 }18 }//for19 cost[0][2] = 10;20 cost[0][4] = 30;21 cost[0][5] = 100;22 cost[2][3] = 50;23 cost[3][5] = 10;24 cost[4][3] = 20;25 cost[4][5] = 60;26 }27 28 /**29 * 获取v到其他顶点最短距离保存到数组dist[]中30 * @param v31 */32 public void shotPath(int v){33 boolean s[] = new boolean[6];//s保存是否已经求出最短距离节点34 35 //初始化36 for(int i = 0; i < 6; i++){37 s[i] = false;38 if(cost[v][i] < max){39 dist[i] = cost[v][i];40 }41 else{42 dist[i] = max;43 }44 }//for45 s[v] = false;46 //开始找到每个节点的最短距离，根据算法思想至少要n - 1次47 for(int i = 0; i < 5; i++){48 int tempMin = max;49 int k = i;//存放最小距离的顶点50 //找出最短的，加入s集合中51 for(int j = 0; j < 6; j++){52 if(!s[j] && dist[j] < tempMin){//在未求出最短距离的集合中找53 tempMin = dist[j];54 k = j;55 }56 }57 s[k] = true;58 //更新dist[]数组59 for(int j = 0; j < 6; j++){60 if(!s[j] && dist[j] > dist[k] + cost[k][j]){61 dist[j] = dist[k] + cost[k][j];62 }63 }64 }65 66 }67 /**68 * 输出矩阵内容69 */70 public void showCost(){71 System.out.println("矩阵内容是：");72 for(int i = 0; i < 6; i++){73 for(int j = 0; j < 6; j++){74 System.out.print(cost[i][j] + "\t");75 }76 System.out.println();77 }//for78 }79 80 /**81 * 测试方法82 * @param args83 */84 public static void main(String args[]){85 Graph graph = new Graph();86 graph.showCost();87 graph.shotPath(0);88 for(int i = 0; i < graph.dist.length;i++){89 System.out.println("顶点0" + "到 顶点" + i + "的最短距离是：" + graph.dist[i]);90 }91 }92 }
Dijkstra算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。