-2

我刚开始使用以下代码的算法

public class Dijkstra {
private static Heap h = new Heap();
private static int[][] g;
int n =6;
public Dijkstra() {
    g = new int[10][10];

    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the weight of each edges (for mobius use 9999)");

    for(int a=1;a<=n;a++)
    {
        for(int b=1;b<=n;b++)
        {
            if((a!=b)&&(a<b))
            {
                System.out.print(a+" and "+b+": ");
                g[b][a] = g[a][b] =sc.nextInt() ;

                if(g[a][b] == 0 )
                {
                    g[b][a] = g[a][b] = 9999;
                }
            }
        if(a==b)
            g[a][b]=9999;
        }
    }
}

public static void main(String[] args) 
{
    Dijkstra dij = new Dijkstra();
    System.out.println(dij.solve(6, 6, 5));
}

public int solve(int numOfNodes, int source, int dest) 
{
    h.push(source, 0);

    while (!h.isEmpty()) 
    {
        int c = h.pop();

        if (c == dest)
            return h.cost[dest];

        for (int a = 0; a < numOfNodes; a++) 
        {
            if (g[c][a] > 0)
                h.push(a, h.cost[c] + g[c][a]);
        }
    }
    return -1;
    }
}

class Heap {
private int[] data;
private int[] index;
public int[] cost;
private int size;
Dijkstra ki = new Dijkstra();

public Heap() 
{
    data = new int[6];
    index = new int[6];
    cost = new int[6];

    for (int a = 0; a < ki.n; a++) 
    {
        index[a] = -1;
        cost[a] = -1;
    }

    size = 0;
}

public boolean isEmpty() 
{
    return (size == 0);
}

private void Up(int a) 
{
    int b;

    while (a > 0) 
    {
        b = (a - 1) / 2;

        if (cost[data[a]] < cost[data[b]]) 
        {
            // swap here
            int temp = index[data[a]];
            index[data[a]] = index[data[b]];
            index[data[b]] = temp;
            // swap here
            temp = data[a];
            data[a] = data[b];
            data[b] = temp;
            a = b;
        } 
        else
            break;
    }
    }

private void Down(int a) 
{
    int b, d;

    while (2 * a + 1 < size) 
    {
        b = 2 * a + 1;
        d = b + 1;

        if (d < size && cost[data[d]] < cost[data[b]]
                && cost[data[d]] < cost[data[a]]) 
        {

            int temp = index[data[d]];
            index[data[d]] = index[data[a]];
            index[data[a]] = temp;

            temp = data[d];
            data[d] = data[a];
            data[a] = temp;

            a = d;
        } 
        else if (cost[data[b]] < cost[data[a]]) 
        {

            int temp = index[data[b]];
            index[data[b]] = index[data[a]];
            index[data[a]] = temp;

            temp = data[b];
            data[b] = data[a];
            data[a] = temp;

            a = b;
        } 
        else
            break;
    }
}

public int pop() 
{
    int i = data[0];
    data[0] = data[size - 1];
    index[data[0]] = 0;
    size--;
    Down(0);
    return i;
}

public void push(int e, int f) 
{
    if (index[e] == 0) 
    {
        cost[e] = f;
        data[size] = e;
        index[e] = size;
        size++;
        Up(index[e]);
    } 
    else 
    {
        if (f < cost[e]) 
        {
            cost[e] = f;
            Up(index[e]);
            Down(index[e]);
        }
        }
     }
 }

我有这个错误，但我不知道我必须在哪里修复它

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
at algo.Heap.push(Dijkstra.java:176)
at algo.Dijkstra.solve(Dijkstra.java:52)
at algo.Dijkstra.main(Dijkstra.java:47)
Java Result: 1

输出将是根和目标之间最短的总权重我想输入其节点的权重使用dijkstra算法有人可以帮我吗

4

4 回答 4

0

你的Heap类数组都有固定的 6 大小（这是错误的，在那里有这样的限制是没有意义的）。

一旦你的算法开始，你调用：

dij.solve(6, 6, 5)   // line 47

依次调用

h.push(6, 0);        // line 52

最后尝试使元素超过index:

if (index[6] == 0)   // line 176

由于index数组有 6 个元素并且 Java 数组是从 0 开始的，这将抛出ArrayIndexOutOfBoundsException.

您需要Fibonacci Heap的有效 Java 实现。

于 2013-08-21T07:19:55.573 回答
0

您只允许数组中总共有 6 个元素，但试图在第 6 个索引处设置一个值。由于索引从零开始，您试图设置超出范围的第 7 个元素。

请参阅本教程。

于 2013-08-21T07:06:23.640 回答
0

有数组：

data = new int[6];
index = new int[6];
cost = new int[6];

有 6 个元素，所以当你使用它们时，例如这里：

cost[e] = f;
data[size] = e;
index[e] = size;

你应该确保 "e" 和 "size" 总是 < 6。

检查第 176 行发生的情况。

于 2013-08-21T07:10:57.973 回答
0

ArrayIndexOutOfBoundsException

当您给定的索引不在数组中时，会发生此异常。

即：如果您有一个包含 6 个元素的数组，并且您正在寻找第 7 个位置的元素它会生成一个 ArrayIndexOutOfBoundsException.

我不在这里回答，因为它很容易解决。

在此处查看更多详细信息ArrayIndexOutOfBoundsException

于 2013-08-21T07:13:35.450 回答