Блог

Как мне найти кратчайший невзвешенный путь, который имеет наименьший взвешенный path…eg если у меня есть два невзвешенных пути A-> B-> C = 2 и A-> D-> F = 2 …. как мне напечатать путь с меньшим весом?

Код для невзвешенного и взвешенного пути выглядит следующим образом:

 public void unweighted( String startName )
{
    clearAll( ); 

    Vertex start = vertexMap.get( startName );
    if( start == null )
        throw new NoSuchElementException( "Start vertex not found" );

    Queue<Vertex> q = new LinkedList<Vertex>( );
    q.add( start ); start.dist = 0;

    while( !q.isEmpty( ) )
    {
        Vertex v = q.remove( );

        for( Edge e : v.adj )
        {
            Vertex w = e.dest;
            if( w.dist == INFINITY )
            {
                w.dist = v.dist   1;
                w.prev = v;
                q.add( w );
            }
        }
    }
}
  

взвешенный:

 public void dijkstra( String startName )
{
    PriorityQueue<Path> pq = new PriorityQueue<Path>( );

    Vertex start = vertexMap.get( startName );
    if( start == null )
        throw new NoSuchElementException( "Start vertex not found" );

    clearAll( );
    pq.add( new Path( start, 0 ) ); start.dist = 0;

    int nodesSeen = 0;
    while( !pq.isEmpty( ) amp;amp; nodesSeen < vertexMap.size( ) )
    {
        Path vrec = pq.remove( );
        Vertex v = vrec.dest;
        if( v.scratch != 0 )  // already processed v
            continue;

        v.scratch = 1;
        nodesSeen  ;

        for( Edge e : v.adj )
        {
            Vertex w = e.dest;
            double cvw = e.cost;

            if( cvw < 0 )
                throw new GraphException( "Graph has negative edges" );

            if( w.dist > v.dist   cvw )
            {
                w.dist = v.dist  cvw;
                w.prev = v;
                pq.add( new Path( w, w.dist ) );
            }
        }
    }
}
  

Итак, я хочу напечатать невзвешенный путь с менее взвешенным путем, пожалуйста, помогите.

Хорошо, я собираюсь приблизиться к этому… Просмотрите свой список невзвешенных путей. Для каждого из них перейдите по структуре пути, суммируя все веса. Выберите тот, у которого наименьшее значение. Ваш код будет выглядеть примерно так, используя типичный шаблон поиска максимума / минимума:

 int minimum = 99999;  // use a value obviously larger than all paths
PathClass minPath = null;

for (PathClass path : unweightedPaths) {
    int total = 0;

    for (PathItemClass item : path) {
        total  = item.weight;
    }

    if (total < minimum) {
        minimum = total;
        minPath = path;
    }
}

// do something with path, which is the smallest weighted path
  

Пожалуйста, дайте мне знать, нахожусь ли я вообще на правильном пути??