数据结构 Dijkstra(迪杰斯特拉)算法
Dijkstra(迪杰斯特拉)算法
是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径,该算法要求图中不存在负权边。
主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
算法思想: 图 G=(V,E) 中,假设每条边E[i]的长度为w[i],找到由顶点V0到其余各点的最短路径
设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组:
第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),
第二组为其余未确定最短路径的顶点集合(用U表示),
按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
每个顶点对应一个距离:
S中的顶点的距离是从v到此顶点的最短路径长度,
U中的顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
算法步骤:
1、初始化:
S只包含源点,即S={v},v的距离为0。
U包含除v外的其他顶点,即:U={其余顶点},
若v与U中顶点u有边,则
import java.io.IOException;
import java.util.Scanner;
public class MatrixUDG2 {
private int mEdgNum; // 边的数量
private char[] mVexs; // 顶点集合
private int[][] mMatrix; // 邻接矩阵
private static final int INF = 100;//Integer.MAX_VALUE; // 最大值
public MatrixUDG2(char[] vexs, int[][] matrix) {
int vlen = vexs.length; // 初始化"顶点数"和"边数"
mVexs = new char[vlen]; // 初始化"顶点"
for (int i = 0; i < mVexs.length; i++)
mVexs[i] = vexs[i];
mMatrix = new int[vlen][vlen]; // 邻接矩阵: 初始化"边" mMatrix[i][j]=1,则表示"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点;mMatrix[i][j]=0,则表示它们不是邻接点
for (int i = 0; i < vlen; i++)
for (int j = 0; j < vlen; j++)
mMatrix[i][j] = matrix[i][j];
// 统计"边"
mEdgNum = 0;
for (int i = 0; i < vlen; i++)
for (int j = i+1; j < vlen; j++)
if (mMatrix[i][j]!=INF)
mEdgNum++;
}
//返回顶点v的第一个邻接顶点的索引,失败则返回-1
private int firstVertex(int v) {
if (v<0 || v>(mVexs.length-1))
return -1;
for (int i = 0; i < mVexs.length; i++)
if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
return i;
return -1;
}
// 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
private int nextVertex(int v, int w) {
if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1))
return -1;
for (int i = w + 1; i < mVexs.length; i++)
if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF)
return i;
return -1;
}
// 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
private int nextVertexs(int v) {
if (v<0 || v>(mVexs.length-1))
return -1;
for (int i=0; i < mVexs.length; i++) {
if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF) {
System.out.print("邻接点"+mVexs[i]+"权重("+mMatrix[v][i]+")");
}
}
return -1;
}
//获取图中的边
private void getEdges() {
System.out.print("edges = "+mEdgNum);
System.out.println();
for (int i=0; i < mVexs.length; i++) {
for (int j=0; j < mVexs.length; j++) {
if (mMatrix[i][j]!=INF && mMatrix[i][j] != 0) {
System.out.println("结点"+mVexs[i]+"和结点"+mVexs[j]+"的边,权重"+mMatrix[i][j]);
}
}
}
System.out.println();
}
/*
* Dijkstra最短路径。
* 即,统计图中"顶点vs"到其它各个顶点的最短路径。
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即,prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中,位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即,dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
public void dijkstra(int vs, int[] prev, int[] dist) {
// flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取
boolean[] flag = new boolean[mVexs.length];
// 初始化
for (int i = 0; i < mVexs.length; i++) {
flag[i] = false; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = mMatrix[vs][i]; // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = true;
dist[vs] = 0;
// 遍历mVexs.length-1次;每次找出一个顶点的最短路径。
int k=0;
for (int i = 1; i < mVexs.length; i++) {
// 寻找当前最小的路径;
// 即,在未获取最短路径的顶点中,找到离vs最近的顶点(k)。
int min = INF;
for (int j = 0; j < mVexs.length; j++) {
if (flag[j]==false && dist[j]<min) {
min = dist[j];
k = j;
//System.out.println("min = "+min+", k ="+k);
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = true;
// 修正当前最短路径和前驱顶点
// 即,当已经"顶点k的最短路径"之后,更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (int j = 0; j < mVexs.length; j++) {
int tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));
if (flag[j]==false && (tmp<dist[j]) ) {
dist[j] = tmp;
//System.out.println("dist[j] = "+dist[j]+", j = "+j);
prev[j] = k;
}
}
}
// 打印dijkstra最短路径的结果
System.out.printf("dijkstra(%c): \n", mVexs[vs]);
for (int i=0; i < mVexs.length; i++)
System.out.printf("shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]);
}
public static void main(String[] args) {
char[] vexs = {
'A', 'B', 'C', 'D', 'E', 'F', 'G'};
int matrix[][] = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}};
int length = vexs.length;
int i=0, j;
System.out.print("结点表: \n");
for(char label:vexs) {
System.out.print("结点"+i+", 标识"+label+"\n");
i++;
}
System.out.print("\n");
System.out.print("邻接矩阵: \n");
for(i=0; i<length; i++){
for(j=0; j<length; j++) {
System.out.printf("%2d ", matrix[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
MatrixUDG2 pG;
pG = new MatrixUDG2(vexs, matrix);
//pG.getEdges();
for(i=0; i<length; i++){
//System.out.printf("顶点%d邻接点%d\n", i, pG.firstVertex(i));
System.out.print("顶点"+vexs[i]);
pG.nextVertexs(i);
System.out.print("\n");
}
System.out.print("\n");
int[] prev = new int[pG.mVexs.length];
int[] dist = new int[pG.mVexs.length];
// dijkstra算法获取"第4个顶点"到其它各个顶点的最短距离
pG.dijkstra(3, prev, dist);
}
}
文章浏览阅读2.9k次,点赞8次,收藏14次。测试主要做什么?这完全都体现在测试流程中,同时测试流程是面试问题中出现频率最高的,这不仅是因为测试流程很重要,而是在面试过程中这短短的半小时到一个小时的时间,通过测试流程就可以判断出应聘者是否合适,故在测试流程中包含了测试工作的核心内容,例如需求分析,测试用例的设计,测试执行,缺陷等重要的过程。..._测试过程管理中包含哪些过程
文章浏览阅读870次,点赞16次,收藏19次。1.背景介绍政府数字化政务是指政府利用数字技术、互联网、大数据、人工智能等新技术手段,对政府政务进行数字化改革,提高政府工作效率,提升政府服务质量的过程。随着人工智能(AI)和机器学习(ML)技术的快速发展,政府数字化政务中的人工智能与机器学习应用也逐渐成为政府改革的重要内容。政府数字化政务的人工智能与机器学习应用涉及多个领域,包括政策决策、政府服务、公共安全、社会治理等。在这些领域,人工...
文章浏览阅读219次,点赞2次,收藏4次。系统主要的用户为用户、管理员,他们的具体权限如下:用户:用户登录后可以对管理员上传的学习视频进行学习。用户可以选择题型进行练习。用户选择小程序提供的考研科目进行相关训练。用户可以进行水平测试,并且查看相关成绩用户可以进行错题集的整理管理员:管理员登录后可管理个人基本信息管理员登录后可管理个人基本信息管理员可以上传、发布考研的相关例题及其分析,并对题型进行管理管理员可以进行查看、搜索考研题目及错题情况。_mysql刷题软件
文章浏览阅读1.4k次。myelipse里有UML1和UML2两种方式,UML2功能更强大,但是两者生成过程差别不大1.建立Test工程,如下图,uml包存放uml类图package com.zz.domain;public class User {private int id;private String name;public int getId() {return id;}public void setId(int..._根据以下java代码画出类图
文章浏览阅读174次。需求:一个topic包含很多个表信息,需要自动根据json字符串中的字段来写入到hive不同的表对应的路径中。发送到Kafka中的数据原本最外层原本没有pkDay和project,只有data和name。因为担心data里面会空值,所以根同事商量,让他们在最外层添加了project和pkDay字段。pkDay字段用于表的自动分区,proejct和name合起来用于自动拼接hive表的名称为 ..._flume拦截器自定义开发 kafka
文章浏览阅读380次。原标题:Java Spring中同时访问多种不同数据库 多样的工作要求,可以使用不同的工作方法,只要能获得结果,就不会徒劳。开发企业应用时我们常常遇到要同时访问多种不同数据库的问题,有时是必须把数据归档到某种数据仓库中,有时是要把数据变更推送到第三方数据库中。使用Spring框架时,使用单一数据库是非常容易的,但如果要同时访问多个数据库的话事件就变得复杂多了。本文以在Spring框架下开发一个Sp..._根据输入的不同连接不同的数据库
文章浏览阅读3.6k次,点赞9次,收藏25次。本案例描述了晶振屏蔽以及开关电源变压器屏蔽对系统稳定工作的影响, 硬件设计时应考虑。_eft电路图
文章浏览阅读1.1k次。对于物料价格的更改,可以采取不同的手段:首先,我们来介绍MR21的方式。 需要说明的是,如果要对某一产品进行价格修改,必须满足的前提条件是: ■ 1、必须对价格生效的物料期间与对应会计期间进行开启; ■ 2、该产品在该物料期间未发生物料移动。执行MR21,例如更改物料1180051689的价格为20000元,系统提示“对于物料1180051689 存在一个当前或未来标准价格”,这是因为已经对该..._mr21 对于物料 zba89121 存在一个当前或未来标准价格
文章浏览阅读7.4k次,点赞3次,收藏13次。[文章导读]联想启天M420是一款商用台式电脑,预装的是win10系统,用户还是喜欢win7系统,该台式机采用的intel 8代i5 8500CPU,在安装安装win7时有很多问题,在安装win7时要在BIOS中“关闭安全启动”和“开启兼容模式”,并且安装过程中usb不能使用,要采用联想win7新机型安装,且默认采用的uefi+gpt模式,要改成legacy+mbr引导,那么联想启天M420台式电..._启天m420刷bios
文章浏览阅读2.7k次,点赞2次,收藏9次。一,为什么要冗余数据互联网数据量很大的业务场景,往往数据库需要进行水平切分来降低单库数据量。水平切分会有一个patition key,通过patition key的查询能..._保证冗余性
文章浏览阅读88次。是时候闭环Java应用了 原创 2016-08-16 张开涛 你曾经因为部署/上线而痛苦吗?你曾经因为要去运维那改配置而烦恼吗?在我接触过的一些部署/上线方式中,曾碰到过以下一些问题:1、程序代码和依赖都是人工上传到服务器,不是通过工具进行部署和发布;2、目录结构没有规范,jar启动时通过-classpath任意指定;3、fat jar,把程序代码、配置文件和依赖jar都打包到一个jar中,改配置..._那么需要把上面的defaultjavatyperesolver类打包到插件中
文章浏览阅读909次。1.得下载一个番茄插件,按alt+g才可以有函数跳转功能。2.不安装番茄插件,按F12也可以有跳转功能。3.进公司的VS工程是D:\sync\build\win路径,.sln才是打开工程的方式,一个是VS2005打开的,一个是VS2013打开的。4.公司库里的线程接口,在CmThreadManager.h 里,这个里面是我们的线程库,可以直接拿来用。CreateUserTaskThre..._番茄助手颜色