java - 最短路径链表

Question

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

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

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

Answer 1

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

邻接列表:列表数组。索引 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;
    }
}