2

ダイクストラのアルゴリズムを使用して、特定の頂点 (v0) から残りの頂点までの最短経路を見つけようとしています。これは解決され、以下のリンクのコードでうまく機能します: http://en.literateprograms.org/index.php?title=Special:DownloadCode/Dijkstra%27s_algorithm_(Java)&oldid=15444

ここにあるようにハードコーディングするのではなく、ユーザー入力から for ループで Edge 配列を割り当てるのに問題があります。

各頂点から Edge[] 隣接関係に新しいエッジを割り当てるのに役立ちますか? 1つまたは複数のエッジである可能性があることに注意してください。

class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }

    public int compareTo(Vertex other){
    return Double.compare(minDistance, other.minDistance);
    }
}


class Edge{
    public final Vertex target;
    public final double weight;

    public Edge(Vertex argTarget, double argWeight){
        target = argTarget; weight = argWeight; }
    }

public static void main(String[] args)
{
    Vertex v[] = new Vertex[3];
    Vertex v[0] = new Vertex("Harrisburg");
    Vertex v[1] = new Vertex("Baltimore");
    Vertex v[2] = new Vertex("Washington");

    v0.adjacencies = new Edge[]{ new Edge(v[1],  1),
                             new Edge(v[2],  3) };
    v1.adjacencies = new Edge[]{ new Edge(v[0], 1),
                             new Edge(v[2],  1),};
    v2.adjacencies = new Edge[]{ new Edge(v[0],  3),
                                 new Edge(v[1],  1)  };

    Vertex[] vertices = { v0, v1, v2};
       /*Three vertices with weight: V0 connects (V1,1),(V2,3)
                                     V1 connects (V0,1),(V2,1)
                                     V2 connects (V1,1),(V2,3)
       */  
    computePaths(v0);
    for (Vertex v : vertices){
    System.out.println("Distance to " + v + ": " + v.minDistance);
    List<Vertex> path = getShortestPathTo(v);
    System.out.println("Path: " + path);
    }
}
}

上記のコードは、v0 から他のすべての頂点への最短パスを見つけるのにうまく機能します。この問題は、新しい edge[] を edge[] 隣接関係に割り当てるときに発生します。

たとえば、これは正しい出力を生成しません。

for (int i = 0; i < total_vertices; i++){
        s = br.readLine();
        char[] line = s.toCharArray();
        for (int j = 0; j < line.length; j++){  
           if(j % 4 == 0 ){ //Input: vertex weight vertex weight: 1 1 2 3
            int vert = Integer.parseInt(String.valueOf(line[j]));
            int w = Integer.parseInt(String.valueOf(line[j+2]));
            v[i].adjacencies = new Edge[] {new Edge(v[vert], w)};
        }
        }
    }

これとは対照的に：

v0.adjacencies = new Edge[]{ new Edge(v[1],  1),
                         new Edge(v[2],  3) };

ユーザー入力を取得して Edge[] を作成し、隣接関係に渡すにはどうすればよいですか? 問題は、エッジが 0 または多数になる可能性があることです。

どんな助けでも大歓迎ですありがとう！

4

1 に答える 1

1

あなたの場合、j の反復ごとに v[i].adjacencies を割り当てています...それは、それが line.length = 8 であることを意味し、v[i].adjacencies は 2 回割り当てられます。それはあなたの意図ではないと思います。

    for (int j = 0; j < line.length; j++){  
       if(j % 4 == 0 ){ //Input: vertex weight vertex weight: 1 1 2 3
        int vert = Integer.parseInt(String.valueOf(line[j]));
        int w = Integer.parseInt(String.valueOf(line[j+2]));
        v[i].adjacencies = new Edge[] {new Edge(v[vert], w)};
    }

コードを次のように変更できます...

    Edge[] edges = new Edge[line.length/4];  
    for (int j = 0; j < line.length; j++){           
       if(j % 4 == 0 ){ //Input: vertex weight vertex weight: 1 1 2 3
        int vert = Integer.parseInt(String.valueOf(line[j]));
        int w = Integer.parseInt(String.valueOf(line[j+2]));
        edges[j/4] =  {new Edge(v[vert], w)};
    }
   v[i].adjacencies = edges;

正確なコードではないかもしれませんが、ループの外側に割り当てる必要があります。

于 2012-12-01T04:59:29.683 に答える