网站建设原码网站服务器的选择有哪几种方式

网站建设原码,网站服务器的选择有哪几种方式,衡水 网站建设,南安网站定制网络延迟时间 问题描述 有 n 个网络节点#xff0c;标记为 1 到 n。 给你一个列表 times#xff0c;表示信号经过有向边的传递时间#xff1a;times[i] (ui, vi, wi)#xff0c;其中 ui 是源节点#xff0c;vi 是目标节点#xff0c;wi 是一个信号从源节点传递到目标节点…网络延迟时间问题描述有n个网络节点标记为1到n。给你一个列表times表示信号经过有向边的传递时间times[i] (ui, vi, wi)其中ui是源节点vi是目标节点wi是一个信号从源节点传递到目标节点的时间。现在从某个节点k发出一个信号。需要多久才能使所有节点都收到信号如果不能使所有节点收到信号返回-1。示例输入: times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2 输出: 2算法思路经典的单源最短路径问题可以使用Dijkstra算法解决。Dijkstra算法核心思想维护一个距离数组dist记录从起始节点到每个节点的最短距离使用优先队列最小堆选择当前距离最短的未处理节点对选中的节点更新其邻居节点的距离重复直到处理完所有可达节点关键建图将输入的边列表转换为邻接表表示初始化起始节点距离为0其他节点距离为无穷大松弛操作通过当前节点更新邻居节点的最短距离结果计算找到所有节点中的最大距离如果有节点不可达则返回-1代码实现方法一Dijkstra算法importjava.util.*;classSolution{/** * 计算从节点k发出信号到达所有节点所需的最长时间 * * param times 有向边列表每个元素为[源节点, 目标节点, 权重] * param n 网络节点总数节点编号1到n * param k 信号起始节点 * return 所有节点收到信号的最短时间如果无法到达所有节点返回-1 */publicintnetworkDelayTime(int[][]times,intn,intk){// 1: 构建邻接表表示的图// graph[i] 存储从节点i出发的所有边每个边用[目标节点, 权重]表示Listint[][]graphnewList[n1];for(inti1;in;i){graph[i]newArrayList();}// 填充邻接表for(int[]edge:times){intuedge[0],vedge[1],wedge[2];graph[u].add(newint[]{v,w});}// 2: 初始化距离数组// dist[i] 表示从起始节点k到节点i的最短距离int[]distnewint[n1];Arrays.fill(dist,Integer.MAX_VALUE);dist[k]0;// 起始节点到自身的距离为0// 3: 使用优先队列实现Dijkstra算法// 优先队列存储[节点, 距离]按距离从小到大排序PriorityQueueint[]pqnewPriorityQueue((a,b)-a[1]-b[1]);pq.offer(newint[]{k,0});// 记录已处理的节点数量boolean[]visitednewboolean[n1];while(!pq.isEmpty()){int[]currentpq.poll();intnodecurrent[0];intdistancecurrent[1];// 如果当前节点已经处理过跳过处理重复入队的情况if(visited[node]){continue;}visited[node]true;// 遍历当前节点的所有邻居for(int[]neighbor:graph[node]){intnextNodeneighbor[0];intweightneighbor[1];// 如果通过当前节点到达邻居的距离更短则更新if(dist[node]weightdist[nextNode]){dist[nextNode]dist[node]weight;pq.offer(newint[]{nextNode,dist[nextNode]});}}}// 4: 计算结果intmaxTime0;for(inti1;in;i){// 如果存在节点不可达返回-1if(dist[i]Integer.MAX_VALUE){return-1;}maxTimeMath.max(maxTime,dist[i]);}returnmaxTime;}}算法分析时间复杂度O((V E) log V)V n节点数E times.length边数每个节点最多入队一次每次堆操作O(log V)每条边最多被处理一次空间复杂度O(V E)邻接表存储O(V E)距离数组O(V)优先队列O(V)算法过程输入times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2初始化邻接表graph[2] [[1,1], [3,1]],graph[3] [[4,1]]距离数组dist [∞, ∞, 0, ∞, ∞]索引0不使用优先队列[(2, 0)]执行过程处理节点2距离0更新节点1dist[1] 0 1 1更新节点3dist[3] 0 1 1队列[(1,1), (3,1)]处理节点1距离1节点1无出边队列[(3,1)]处理节点3距离1更新节点4dist[4] 1 1 2队列[(4,2)]处理节点4距离2节点4无出边队列为空最终距离dist [∞, 1, 0, 1, 2]最大距离max(1, 0, 1, 2) 2测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[][]times1{{2,1,1},{2,3,1},{3,4,1}};System.out.println(Test 1: solution.networkDelayTime(times1,4,2));// 2// 测试用例2无法到达所有节点int[][]times2{{1,2,1}};System.out.println(Test 2: solution.networkDelayTime(times2,2,2));// -1// 测试用例3单个节点int[][]times3{};System.out.println(Test 3: solution.networkDelayTime(times3,1,1));// 0// 测试用例4复杂网络int[][]times4{{1,2,1},{2,3,2},{1,3,4}};System.out.println(Test 4: solution.networkDelayTime(times4,3,1));// 3// 测试用例5包含环路但不影响最短路径int[][]times5{{1,2,1},{2,1,3},{2,3,2},{3,4,1}};System.out.println(Test 5: solution.networkDelayTime(times5,4,1));// 4// 测试用例6大权重边int[][]times6{{1,2,100},{2,3,100},{3,4,100}};System.out.println(Test 6: solution.networkDelayTime(times6,4,1));// 300// 测试用例7多条路径到同一节点int[][]times7{{1,2,1},{1,3,4},{2,3,2},{2,4,6},{3,4,3}};System.out.println(Test 7: solution.networkDelayTime(times7,4,1));// 6}关键点图使用邻接表而非邻接矩阵节省空间邻接表索引从1开始对应节点编号优先队列始终选择当前距离最短的未处理节点保证每次处理的都是最优解贪心策略重复入队处理同一节点可能多次入队距离更新时通过visited数组或距离比较避免重复处理不可达节点距离仍为Integer.MAX_VALUE表示不可达只要有1个不可达节点就返回-1结果需要所有节点都收到信号所以取最大距离起始节点自身距离为0不影响结果常见问题为什么使用Dijkstra而不是其他最短路径算法传递时间都是正数Dijkstra最适合如果有权重为负的情况需要使用Bellman-Fordvisited数组使用visited数组可以减少堆操作次数提高效率如何处理节点编号从1开始创建大小为n1的数组忽略索引0