gpt4 book ai didi

java - 最短路径链表

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:31:02 26 4
gpt4 key购买 nike

我想在链表列表中找到最短路径,它表示具有每条边/路径成本的有向图。

输出 看起来像这样,它告诉我从顶点 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/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com