package algorithm;
import java.util.Arrays;
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
// 构建邻接表,用于存放各个点到各个点的距离
int[][] graph = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
graph[i][j] = -1;
}
}
// 遍历times填充邻接表
for (int[] time : times) {
graph[time[0]][time[1]] = time[2];
}
// 存放 K 到各个点的最短路径,最大的那个最短路径即为结果
int[] distance = new int[N + 1];
Arrays.fill(distance, -1);
// 初始化 distance 为 K 到各个节点的距离
for (int i = 1; i <= N; i++) {
distance[i] = graph[K][i];
}
// K到达K本身的节点初始化为 0
distance[K] = 0;
// 判断是否找到K到达该点最短路径
boolean[] visited = new boolean[N + 1];
visited[K] = true;
// 遍历除K本身节点之外的所有N-1个节点
for (int i = 1; i <= N - 1; i++) {
int minDistance = Integer.MAX_VALUE;
int minIndex = 1;
// 遍历所有节点,找到离K最近的节点
for (int j = 1; j <= N; j++) {
if (!visited[j] && distance[j] != -1 && distance[j] < minDistance) {
minDistance = distance[j];
minIndex = j;
}
}
// 标记最近距离节点找到
visited[minIndex] = true;
// 根据刚刚找到的最短距离节点,通过该节点更新K节点与其他的节点的距离
for (int j = 1; j <= N; j++) {
// 如果已更新的最短节点可以到达当前节点
if (graph[minIndex][j] != -1) {
if (distance[j] != -1) {
// 取之前路径与当前更新路径的最小值
distance[j] = Math.min(distance[j], distance[minIndex] + graph[minIndex][j]);
} else {
// 该节点是第一次访问,直接更新
distance[j] = distance[minIndex] + graph[minIndex][j];
}
}
}
}
int maxDistance = 0;
// 遍历最大值,如果有节点未被访问,返回 -1,否则返回最大最短路径
for (int i = 1; i <= N; i++) {
if (distance[i] == -1) {
return -1;
}
maxDistance = Math.max(distance[i], maxDistance);
}
return maxDistance;
}
}
作者:hncboy
链接:https://leetcode-cn.com/problems/network-delay-time/solution/java-shi-xian-dijkstra-floyd-bellman-ford-spfa-by-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
/*
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class Dijkstra {
public static void main(String[] args) {
Graph g = new Graph();
g.addVertex('A', Arrays.asList(new Vertex('B', 7), new Vertex('C', 8)));
g.addVertex('B', Arrays.asList(new Vertex('A', 7), new Vertex('F', 2)));
g.addVertex('C', Arrays.asList(new Vertex('A', 8), new Vertex('F', 6), new Vertex('G', 4)));
g.addVertex('D', Arrays.asList(new Vertex('F', 8)));
g.addVertex('E', Arrays.asList(new Vertex('H', 1)));
g.addVertex('F', Arrays.asList(new Vertex('B', 2), new Vertex('C', 6), new Vertex('D', 8), new Vertex('G', 9), new Vertex('H', 3)));
g.addVertex('G', Arrays.asList(new Vertex('C', 4), new Vertex('F', 9)));
g.addVertex('H', Arrays.asList(new Vertex('E', 1), new Vertex('F', 3)));
System.out.println(g.getShortestPath('A', 'H'));
}
}
class Vertex implements Comparable<Vertex> {
private Character id;
private Integer distance;
public Vertex(Character id, Integer distance) {
super();
this.id = id;
this.distance = distance;
}
public Character getId() {
return id;
}
public Integer getDistance() {
return distance;
}
public void setId(Character id) {
this.id = id;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((distance == null) ? 0 : distance.hashCode());
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (distance == null) {
if (other.distance != null)
return false;
} else if (!distance.equals(other.distance))
return false;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
return true;
}
@Override
public String toString() {
return "Vertex [id=" + id + ", distance=" + distance + "]";
}
@Override
public int compareTo(Vertex o) {
if (this.distance < o.distance)
return -1;
else if (this.distance > o.distance)
return 1;
else
return this.getId().compareTo(o.getId());
}
}
class Graph {
private final Map<Character, List<Vertex>> vertices;
public Graph() {
this.vertices = new HashMap<Character, List<Vertex>>();
}
public void addVertex(Character character, List<Vertex> vertex) {
this.vertices.put(character, vertex);
}
public List<Character> getShortestPath(Character start, Character finish) {
final Map<Character, Integer> distances = new HashMap<Character, Integer>();
final Map<Character, Vertex> previous = new HashMap<Character, Vertex>();
PriorityQueue<Vertex> nodes = new PriorityQueue<Vertex>();
for(Character vertex : vertices.keySet()) {
if (vertex == start) {
distances.put(vertex, 0);
nodes.add(new Vertex(vertex, 0));
} else {
distances.put(vertex, Integer.MAX_VALUE);
nodes.add(new Vertex(vertex, Integer.MAX_VALUE));
}
previous.put(vertex, null);
}
while (!nodes.isEmpty()) {
Vertex smallest = nodes.poll();
if (smallest.getId() == finish) {
final List<Character> path = new ArrayList<Character>();
while (previous.get(smallest.getId()) != null) {
path.add(smallest.getId());
smallest = previous.get(smallest.getId());
}
return path;
}
if (distances.get(smallest.getId()) == Integer.MAX_VALUE) {
break;
}
for (Vertex neighbor : vertices.get(smallest.getId())) {
Integer alt = distances.get(smallest.getId()) + neighbor.getDistance();
if (alt < distances.get(neighbor.getId())) {
distances.put(neighbor.getId(), alt);
previous.put(neighbor.getId(), smallest);
forloop:
for(Vertex n : nodes) {
if (n.getId() == neighbor.getId()) {
nodes.remove(n);
n.setDistance(alt);
nodes.add(n);
break forloop;
}
}
}
}
}
return new ArrayList<Character>(distances.keySet());
}
}*/
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何具体存储。例如,数组的连续存储,链表的动态分配节点,树和图的邻接矩阵或邻接表表示等。 基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,使得计算机可以执行以求解问题。 算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界法等。 算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
资源推荐
资源详情
资源评论
收起资源包目录
java实现基础的数据结构和算法.zip (46个子文件)
open_suanfayushujujiegouxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxcxvcvcv
code
lib
algs4.jar 1.08MB
.classpath 346B
.settings
org.eclipse.jdt.core.prefs 587B
src
algorithm
Dijkstra.java 7KB
BinarySearch.java 768B
Stack.java 1KB
BST.java 618B
datastructure
GraphTraversal.java 2KB
TreeTraversal.java 784B
BFSTraversal.java 131B
LinkedListStack.java 1KB
PriorityQueue.java 2KB
ArrayStack.java 2KB
ArrayQueue.java 1KB
ListGraph.java 1KB
MaxHeap.java 3KB
LinkedListQueue.java 1006B
HashMap.java 4KB
LinkedList.java 3KB
BST.java 5KB
bin
algorithm
BST.class 1KB
BinarySearch.class 1KB
Stack$Node.class 632B
BST$Node.class 2KB
Solution.class 508B
Stack.class 2KB
datastructure
LinkedList.class 3KB
LinkedList$ListNode.class 446B
ArrayStack.class 2KB
PriorityQueue.class 2KB
LinkedListQueue.class 1KB
BST.class 3KB
BST$TreeNode.class 436B
HashMap.class 4KB
HashMap$HashNode.class 820B
LinkedListQueue$QueueNode.class 471B
LinkedListStack$StackNode.class 469B
BFSTraversal.class 407B
MaxHeap.class 3KB
PriorityQueue$Node.class 497B
GraphTraversal.class 3KB
ListGraph.class 2KB
LinkedListStack.class 2KB
ArrayQueue.class 2KB
TreeTraversal.class 1KB
.project 394B
共 46 条
- 1
资源评论
极致人生-010
- 粉丝: 2923
- 资源: 2826
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 微软常用运行库 游戏运行库 VC++各个版本
- 微信小程序开发教程.pptx
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- 锐捷网络认证中心网络管理.pdf
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- SD8233LF是一款用于单按键触摸及接近感应开关,其用途是替代传统的机械型开关芯片IC
- 基于YOLOv5的烟雾火焰检测算法研究
- 基于STM32的联合调试侦听设备解决方案原理图PCB源文件调试工具视频(大赛作品)
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功