- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我想在链表列表中找到最短路径,它表示具有每条边/路径成本的有向图。
输出 看起来像这样,它告诉我从顶点 0 到其他顶点所需的成本:
d[0 to 0] = 0
d[0 to 1] = 20
d[0 to 2] = 10
这就是我填充列表以进行测试的方式。
LinkedList<GraphData> g = new LinkedList[3];
for (int i = 0; i < 3; i++)
weight[i] = new LinkedList<GraphData>();
g[0].add(new GraphData(1, 20);
g[0].add(new GraphData(2, 10);
GraphData 类 看起来像这样:
int vertex, int edgeCost;
现在解决我的问题:
我想找到从顶点 v 到所有其他顶点的最短路径。
public static int[] shortestPaths(int v, LinkedList<GraphData>[] cost)
{
// get the set of vertices
int n = cost.length;
// dist[i] is the distance from v to i
int[] dist = new int[n];
// s[i] is true if there is a path from v to i
boolean[] s = new boolean[n];
// initialize dist
for(int i = 0; i < n; i++)
dist[i] = cost[v].get(i).getCost();
s[v] = true;
// determine n-1 paths from v
for ( int j = 2 ; j < n ; j++ )
{
// choose u such that dist[u] is minimal for all w with s[w] = false
// and dist[u] < INFINITY
int u = -1;
for (int k = 0; k < n; k++)
if ( !s[k] && dist[k] < INFINITY)
// check if u needs updating
if ( u < 0 || dist[k] < dist[u])
u = k;
if (u < 0)
break;
// set s[u] to true and update the distances
s[u]=true;
for (int k = 0; k < n; k++)
if ( !s[k] && cost[u].get(k).getCost() < INFINITY )
if( dist[k] > dist[u] + cost[u].get(k).getCost())
dist[k] = dist[u] + cost[u].get(k).getCost();
// at this point dist[k] is the smallest cost path from
// v to k of length j.
}
return dist;
}
这一行 dist[i] = cost[v].get(i).getCost();抛出“IndexOutOfBoundsException”
知道我做错了什么吗?任何帮助将不胜感激。
最佳答案
有两种常用的图表示方式:邻接表和邻接矩阵。
邻接列表:列表数组。索引 i
处的元素是一个包含顶点 i
的出边的小列表。这就是您在填充列表时创建的内容。
邻接矩阵:数组的数组,cost[i][j]
包含从顶点i
到顶点的边的成本j
。您正在使用 cost
参数,就好像它是一个邻接矩阵一样。
你有两个选择:
cost
视为邻接列表而不是邻接矩阵这是第二个选项。我重命名了一些东西并简化了初始化,以便第一次迭代计算到 v
的直接邻居的距离(而不是在开始时将其作为特例)。
import java.util.*;
public class Main
{
public static int[] shortestPaths(int v, LinkedList<Edge>[] edges)
{
// get the set of vertices
int n = edges.length;
// dist[i] is the distance from v to i
int[] dist = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = Integer.MAX_VALUE;
}
// seen[i] is true if there is a path from v to i
boolean[] seen = new boolean[n];
dist[v] = 0;
// determine n-1 paths from v
for (int j = 0; j < n; j++) {
// choose closest unseen vertex
int u = -1;
for (int k = 0; k < n; k++) {
if (!seen[k]) {
// check if u needs updating
if (u < 0 || dist[k] < dist[u]) {
u = k;
}
}
}
if (u < 0 || dist[u] == Integer.MAX_VALUE) {
break;
}
// at this point dist[u] is the cost of the
// shortest path from v to u
// set seen[u] to true and update the distances
seen[u] = true;
for (Edge e : edges[u]) {
int nbr = e.getTarget();
int altDist = dist[u] + e.getCost();
dist[nbr] = Math.min(dist[nbr], altDist);
}
}
return dist;
}
public static void main(String[] args)
{
int n = 5;
int start = 0;
LinkedList<Edge>[] cost = new LinkedList[n];
for (int i = 0; i < n; i++) {
cost[i] = new LinkedList<Edge>();
}
cost[0].add(new Edge(1, 20));
cost[0].add(new Edge(2, 10));
cost[1].add(new Edge(3, 5));
cost[2].add(new Edge(1, 6));
int[] d = shortestPaths(start, cost);
for (int i = 0; i < n; i++) {
System.out.print("d[" + start + " to " + i + "] = ");
System.out.println(d[i]);
}
}
}
class Edge
{
int target, cost;
public Edge(int target, int cost) {
this.target = target;
this.cost = cost;
}
public int getTarget() {
return target;
}
public int getCost() {
return cost;
}
}
关于java - 最短路径链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16075150/
这个问题在这里已经有了答案: Integer summing blues, short += short problem (5 个答案) 关闭 7 年前。 版本:Visual Studio Prof
我尝试执行以下代码: public class Test5 { /** * @param args */ public static void main(String[] args) {
这是我的任务,我尝试仅使用简短的 if 语句来完成此任务,我得到的唯一错误是使用“(0.5<=ratio<2 )”,除此之外,构造正确吗? Scanner scn = new Scanner(
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我有一个简单的类型 data Day = Monday | Tuesday | Wednesday | Thursday | Friday 我是haskell的新手,所以我写==如下。 (==) :
如何实现“简短”和“详细”两个按钮? “短”应该是默认值,并显示页面的一个版本。单击“详细”按钮后,应显示该页面的另一个版本。 由于这有点难以解释,或许可以看下面的例子。 示例页面: 别管内容 需要j
有没有一种方法可以在 C# 中执行此操作,而无需为现有的每个 var 类型创建一个新方法来重载? $box = !empty($toy) : $toy ? ""; 我能想到的唯一方法是: if (t
我想使用 setInterval 创建一个节拍器。我希望能够达到 300 bpm 这样的高 bpm。即使文件足够短,可以根据需要播放多次,它也很容易 打嗝。此外,许多浏览器都存在短音频文件的问题——S
我们现在有一个正在生产中的应用程序,它会将 IAP 收据发送到我们的服务器,这些收据显然太短,而且我们的服务器没有经过 apple 的验证。 Apple 正确验证的长收据长度为 3192。短收据长度均
例如,许多软件使用的许可证 key 。我曾想过对一个序列进行密码签名,所以我可能有 4 个字节用于 ID,8 个字节用于签名,但我找不到合适的算法。 我需要的是攻击者无法轻易生成,但存储在大约 20
作为一个学生项目,我们正在构建一个机器人,它应该跑完规定的路线并捡起一个木制立方体。它的核心是一台运行 debian 的单板计算机,配备 ARM9,频率为 250MHz。因此 Controller 的
在将 short 转换为字节数组时,我在网上找到了以下解决方案,但不太理解所涉及的逻辑。 //buffer is an array of bytes, bytes[] buffer[position]
如何在 PHP namespace 环境中检查对象的类而不指定完整的命名空间类。 例如,假设我有一个对象库/实体/契约(Contract)/名称。 以下代码不起作用,因为 get_class 返回完整
我有一个 View 范围的托管 bean,其托管属性绑定(bind)到查询字符串参数。 JSF 给了我熟悉的异常: javax.faces.FacesException: Property reset
根据 this post我已经修复了对象检查器。有时代码可以很好地运行 10 个条目,使它们全部正确,有时它可以运行 5 个条目。有时它会导致条目错误。 在获取元素的内部文本时总是会失败。当它的 Y/
我正在编写一组工具,其中 C++ 应用程序使用 AES 加密标准对数据进行编码,而 Java 应用程序对其进行解码。据我所知, key 长度必须为 16 个字节。但是当我尝试使用不同长度的密码时,我遇
我有以下代码: short num_short = 1; int possible_new_short = 1; valid = 1; while (valid) { poss
因此,作为 C 的新手,我遇到了我的第一个 SIGSEGV 错误。它出现在一个简短的 C 程序中,该程序旨在成为“猜数字”游戏。它由一个比较两个数字的自定义函数和一个带有输入的 do-while 循环
我不是严格意义上的初级程序员,但我没有接受过数学以外的正规教育 - 所以这纯粹是业余爱好,可能是业余的。 我最近自己开发了一个算法来解决这个问题,但我想知道是否有任何相对简单的算法明显更高效/更快?
我正在使用短条件来区分记录列表中显示的值。 例如,如果我希望强调 ( ) 标识符大于 100 的客户的姓名,请执行以下操作: {# Displays the identifier of the c
我是一名优秀的程序员,十分优秀!