我想在一个链表列表中找到最短路径，它代表一个有向图，每条边/路径的成本。
输出应该是这样的，它告诉我从顶点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);
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;
}
This line 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;
}
}
元素cost[v].get(i)可能不存在(LinkedList即cost[v]中没有索引为i的元素)
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html get (int)
问题是您的索引不对应。如果你只放一个距离，比如
cost[0].add(new GraphData(5, 20));
cost[0].get(5).getCost();
将抛出IndexOutOfBoundsException，因为您应该执行
cost[0].get(0).getCost();
为了得到20(这是非常令人困惑的)。
我建议使用Map而不是List来编码边缘成本。
将Map填充为
List<Map<Integer, Integer>> g = new ArrayList<>();
for (int i = 0; i < 3; i++)
g.add(new HashMap<Integer, Integer>());
g.get(0).put(1, 20);
g.get(0).put(2, 10);
dist数组// initialize dist
for(int i = 0; i < n; i++)
dist[i] = cost.get(v).containsKey(i) ? cost.get(v).get(i) : INFINITY;