0

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

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

知道我做错了什么吗？任何帮助将不胜感激。

4

3 回答 3

1

表示图的常用方法有两种：邻接表和邻接矩阵。

邻接列表：列表数组。index 处的元素i是一个包含 vertex 的出边的小列表i。这是您在填充列表时创建的内容。

邻接矩阵：数组数组，包含从 vertex到 vertexcost[i][j]的边的成本。您正在使用该参数，就好像它是一个邻接矩阵。ijcost

你有两个选择：

  • 更改图形构造以创建邻接矩阵并使用数组数组
  • 更改算法以将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;
    }
}
于 2013-04-18T06:57:44.600 回答
0

可能元素cost[v].get(i)不存在（i在 this LinkedListis中没有具有索引的元素cost[v]）。

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html#get(int)

于 2013-04-18T05:45:50.653 回答
0

问题是您的索引不对应。例如，如果您只设置一个距离

cost[0].add(new GraphData(5, 20));

然后

cost[0].get(5).getCost();

会抛出一个IndexOutOfBoundsException，因为你应该这样做

cost[0].get(0).getCost();

为了得到20（这很令人困惑）。

我建议使用 a Map，而不是 aList来编码边缘成本。

你填充那个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;
于 2013-04-18T09:11:42.850 回答