程序员经验分享-hwhale

Dijkstra 算法适用于有向图还是无向图？

2023-12-22

我一直试图用谷歌搜索这个，但我发现的结果只会增加我的困惑。好像两者都可以用？如果是这样，它的默认设计目的是什么？需要进行哪些更改才能使其以非默认方式工作（无论是定向还是非定向）？

编辑：仅供参考，上学期我遇到了一个问题，我得到了这样的列表（机场）：

AER,KZN,1.8835
ASF,KZN,1.3005
ASF,MRV,1.1204
CEK,KZN,1.9263
CEK,OVB,1.6733
DME,KZN,1.7892
DME,NBC,2.2319
DME,UUA,2.3786
EGO,KGD,1.4649
EGO,KZN,1.2603
GYD,NBC,2.0755

有人告诉我这是有方向的，并要求我找到最短路线。我把它放入我在 Github 上找到的 Dijkstra 算法中（这是一次开放计算机期中考试，所以我们没有足够的时间从头开始编写算法），我的教授说它返回的最短路径不正确，而且它是甚至没有可能的路径，因为列表应该是有向的。我不确定我是否应该修改算法或列表来进行此更正。最终的情况是，它返回的第二条最短路径实际上是有向最短路径，但我仍然想知道问题是什么。


它可以应用于两者。原因如下：

An 无向的图基本上与a相同directed图形与双向连接节点之间的连接（= 两个方向相反的连接）。

因此，您实际上不必执行任何操作即可使其适用于无向图。您只需要知道从每个给定节点可以通过例如到达的所有节点。一个邻接表.

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

Algorithm

Graph

Dijkstra

Dijkstra 算法适用于有向图还是无向图？ 的相关文章

  • 在 3d 网格中转发（绘制）线

    我需要类似 Bresenham 算法的东西 但是 对于 3d 网格空间来说不完全是这样 我需要 3d 单元网格 边缘尺寸 1 0 从 S 点开始 前进到 K 点 接触 该线接触的所有单元格 即使只有边缘 点被触摸我需要触摸所有 8 个单元

  • 计算字符串的所有子串中子序列的出现次数

    我想编写一个算法来计算字符串的所有子字符串中字符子序列 不相交 出现的总数 下面是一个例子 字符串 jabcohnnyjohnny 后续 约翰尼 包含子序列的子字符串 jabcohnny jabcohnnyj jabcohnnyjo jab

  • 线段树java实现[关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 你知道 二进制 的良好实现吗线段树 http en wikipedia org wiki Segmen

  • 定点数学比浮点运算快吗？

    多年前 即 20 世纪 90 年代初期 我构建了图形软件包 该软件包基于定点算术和预先计算的 cos sin 表格以及使用牛顿近似方法进行 sqrt 和对数近似的缩放方程来优化计算 这些先进技术似乎已经成为图形和内置数学处理器的一部分 大约

  • 自动跟踪算法

    我正在尝试写一个simple跟踪例程来跟踪电影中的某些点 本质上我有一系列 100 帧长的电影 在黑暗背景上显示一些亮点 我每帧有大约 100 150 个点 它们在电影的过程中移动 我想跟踪它们 所以我正在寻找一些有效的 但可能不会过度实施

  • 数独算法，暴力破解[关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我正在尝试

  • 什么是“朴素”算法，什么是“封闭式”解决方案？

    我有一些关于描述算法时使用的术语语义的问题 首先 朴素 算法是什么意思 这与给定问题的其他解决方案有何不同 解决方案还可以采取哪些其他形式 其次 我听到很多人提到 封闭式 解决方案 我也不知道这意味着什么 但在尝试解决递归关系时经常会出现

  • 如何在 C# 中以编程方式创建柔和的颜色？

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

  • 绘制点之间的所有线

    我有以下 R 代码 x lt c 0 01848598 0 08052353 0 06741172 0 11652034 y lt c 0 4177541 0 4042247 0 3964025 0 4074685 d lt data fr

  • LRU算法，实现这个算法需要多少位？

    我有一个关于 LRU 算法的小问题 如果您有一个包含四个块的高速缓存 那么需要多少位来实现该算法 假设您指的是 4 路组关联缓存 完美 LRU 本质上是按照使用顺序为每一行分配一个精确的索引 您也可以将其视为 年龄 因此 4 个元素中的每一

  • 如何在C中实现带连分数的自然对数？

    这里我有一个小问题 根据这个公式创建一些东西 这就是我所拥有的 但它不起作用 弗兰基 我真的不明白它应该如何工作 我尝试用一 些错误的指令对其进行编码 N 是迭代次数和分数部分 我认为它会以某种方式导致递归 但不知道如何 谢谢你的帮助 do

  • Java 2d 游戏中的路径查找？

    本质上它是我正在开发的一款吃豆人克隆游戏 我有一个 Enemy 类 并创建了该类的 4 个实例 它们都代表游戏的 4 个幽灵 所有幽灵都会在屏幕的随机区域启动 然后它们必须朝着吃豆人角色前进 当玩家控制吃豆人并移动它时 他们应该跟随它并尽可

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

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

  • 总和不小于 key 的数组的最小子集

    给定一个数组 假设为非负整数 我们需要找到最小长度子集 使得元素之和不小于 K K 是作为输入提供的另一个整数 是否有可能找到时间复杂度为 O n n 的大 oh 的解决方案 我目前的想法是这样的 我们可以在 O n log n 中对数组进

  • 求先递增后递减列表的最大值和最小值

    我尝试用谷歌搜索这个问题 但没有取得太大成功 我确信这个问题或类似问题有一个技术名称 但我似乎找不到答案 给定一个列表L整数 即严格递增 然后严格递减 找到该列表的最大值和最小值 例如 L可能 1 2 3 4 5 4 3 2 or 2 4

  • 在 NetworkX 中使边缘更粗

    student id 0 1 2 3 4 5 6 7 8 9 10 11 12 0 131X1319 1 14 6 16 1 10 8 15 15 17 15 18 16 1 13212YX3 1 1 4 8 11 9 14 7 0 3 0

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

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

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

    问题陈述 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 剪枝算法来实现 所以 我阅读了这些算法 现在了解了游戏将如何解决 但是当我坐下来编写代码时 我面临着

  • Java 中旅行商问题的暴力算法

    我正在学校的数学课上做一个项目 我选择做旅行商问题 这是我一直想进行更多研究的问题 但是 我的暴力求解算法遇到了问题 请前往底部更新查看最新版本代码 如果您知道旅行推销员问题是什么 请跳过本段 尽可能概括地说 TSP 是这样的 您是一名推销

随机推荐

热门标签