程序员经验分享-hwhale

寻找等权图的最短路径

2023-12-21

我有一个权重相等的图表。我怎样才能找到最短路径？ 我们可以用DijKstra's Algorithm并找到最短路径。我认为在这种情况下会使用回溯。但是，当图的权重相等时，还有其他方法可以找到最佳的最短路径吗？


BFS 是获得从一个节点到另一个节点的最短路径的最佳方法...它首先找到距离为 1 的所有节点，然后是距离 2 的节点，依此类推

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

languageagnostic

寻找等权图的最短路径 的相关文章

  • 是否有一种算法可以在线性时间内计算数组反转？

    我知道有多少倒转 en wikipedia org wiki Inversion 28discrete mathematics 29 in an n 元素数组可以在 O n log n 操作使用增强型归并排序 http www geeksf

  • 坐标算法 - 绕中心旋转

    通过查看这张图片 我想您会很好地理解我的问题 图片已删除 网址不再有效 现在返回广告 所以基本上我想要一个函数 它接受一个对象作为参数 并根据我之前添加的对象数量为该对象提供正确的坐标 假设我将所有这些对象添加到一个数组中 objectAr

  • 重写修改后的 goto 语义的算法

    我有一大堆使用旧的自行设计的脚本语言编写的遗留代码 我们将它们编译 翻译成 javascript 该语言有条件跳转 跳转到标签 与普通 goto 语句的区别在于 不可能向后跳转 该语言中没有嵌套的 if 语句或循环 由于 javascrip

  • 是否有加权水库采样的算法？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 当数据流中的点具有相关权重时 是否有一种算法可以执行水库采样 Pavlos Efraimidis 和 Paul Spirakis 的算

  • 我应该对算法使用递归还是记忆化？

    如果我可以选择使用递归或记忆来解决问题 我应该使用哪一个 换句话说 如果它们都是可行的解决方案 因为它们提供了正确的输出并且可以在我正在使用的代码中合理地表达 那么我什么时候会使用其中一个而不是另一个 它们并不相互排斥 您可以同时使用它们

  • JavaScript 中的埃拉托斯特尼筛法对大量数据无限运行

    我一直在尝试写埃拉托斯特尼筛法 http en wikipedia org wiki Sieve of EratosthenesJavaScript 中的算法 基本上我只是按照以下步骤操作 创建从 2 到 n 1 的连续整数列表 令第一个素

  • 奖励*完整*初学者的代码项目[关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 为刚接触编程的人提供的课程通常包括一个代码项目 我认为这是一种很好的学习方式 然而 这样的项目往往让人感觉过于做作 因此做起来并没有多大回

  • 在一个区域中拟合二维多边形的算法？

    这有标准吗 算法名称 说 我有 10 个不同大小的多边形 我有一个特定大小的区域 我想知道如何填充该区域中的最多多边形 以及它们是如何拟合的 笔记 多边形可以根据限制集进行旋转 一个可能的名称是包装问题 http en wikipedia

  • 面试题：三个数组，O(N*N)

    假设我们有three长度数组N其中包含任意数量的类型long 然后我们得到一个数字M 相同类型 我们的任务是选择三个数字A B and C每个数组中的一个 换句话说A should从第一个数组中选取 B从第二个开始和C从第三个 所以总和A

  • 排序矩阵的选择算法

    这是谷歌面试问题 给定一个 N N 矩阵 所有行均已排序 所有列均已排序 找到矩阵的第 K 个最大元素 在 n 2 中执行它很简单 我们可以使用堆或合并排序 n lg n 对它进行排序 然后得到它 但是有没有更好的方法 比 n lg n 更

  • 计算序列而无法存储值？

    问题陈述 here http www spoj com problems EC SER 令 S 为无限整数序列 S0 a S1 b Si Si 2 Si 1 对于所有 i gt 2 你有两个整数 a 和 b 您必须回答有关序列中第 n 个元

  • 我如何开始玩五子棋？

    我读到Gomoku http en wikipedia org wiki Gomoku它可以使用 Minimax 和 Alpha Beta 剪枝算法来实现 所以 我阅读了这些算法 现在了解了游戏将如何解决 但是当我坐下来编写代码时 我面临着

  • 在 Python 中从 Excel 复制 YEARFRAC() 函数

    因此 我使用 python 来自动执行一些必须在 Excel 中执行的重复任务 我需要做的计算之一需要使用yearfrac 这在Python中被复制了吗 I found this https lists oasis open org arc

  • 从给定的项目列表创建子列表

    我首先要说的是以下问题不是为了家庭作业目的即使因为我几个月前就完成了软件工程师的工作 无论如何 今天我正在工作 一位朋友向我询问了这个奇怪的排序问题 我有一个包含 1000 行的列表 每行代表一个数字 我想创建 10 个子列表 每个子列表都

  • while循环的时间复杂度是多少？

    我正在尝试找出 while 循环的时间复杂度 但我不知道从哪里开始 我了解如何找到 for 循环的复杂性类别 但是当涉及到 while 循环时 我完全迷失了 关于从哪里开始有什么建议 提示吗 这是一个问题的示例 x 0 A n some a

  • 如何实现n个元素的查找和插入操作的动态二分查找

    这个想法是使用多个数组 每个长度为 2 k 根据 n 的二进制表示来存储 n 个元素 每个数组都是排序的 不同的数组没有以任何方式排序 在上述数据结构中 SEARCH是通过对每个数组进行一系列二分查找来进行的 INSERT 是通过一系列相同

  • 确定一组日期的事件重复模式

    我正在寻找一种模式 算法或库 它将采用一组日期并在退出时返回重复的描述 即集合 11 01 2010 11 08 2010 11 15 2010 11 22 2010 11 29 2010 会产生类似 十一月的每个星期一 的结果 有没有人以

  • Java中的对象池模式

    所以我实现了自己的对象池模式 它工作得很好并且符合预期 从列表中返回我的 老师 对象 并在没有对象时创建它们 我的问题 返回的对象 Teacher 然后需要被转换为它的专门子类之一 例如 生物老师 获得这种功能的最佳方法是什么 编辑 抱歉

  • 图算法：邻接图的可达性

    我有一个依赖图 我将其表示为Map

  • 最小硬币找零问题——回溯

    我正在尝试用最少数量的硬币解决硬币找零问题 采用回溯法 我实际上已经完成了它 但我想添加一些选项 按其单位打印硬币数量 而不仅仅是总数 这是我下面的Python代码 def minimum coins coin list change mi

随机推荐

热门标签