Невзвешенный кратчайший путь - PullRequest
Новая
       24

Невзвешенный кратчайший путь

0 голосов
/ 11 мая 2011

Как мне найти кратчайший невзвешенный путь, который имеет кратчайший взвешенный путь ... например, если у меня есть два невзвешенных пути 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 );
            }
        }
    }
}

weighted: 

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( ) && 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 ) );
            }
        }
    }
}

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

1 Ответ

1 голос
/ 11 мая 2011

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

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

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

...