1 shortest path problem

Abstraction of shortest path problem

  • In the network, find the path with the least sum of the weights of the edges among all paths between two different vertices
    • This path is the shortest path between two points
    • The first vertex is the source point
    • The last vertex is the end point

Problem classification

  • Single source shortest path problem: from a fixed source point, find the shortest path to all other vertices
    • (directed) unauthorized map
    • Power map
  • Multi source shortest path problem: finding the shortest path between any two vertices

Single source shortest path algorithm for powerless graph

  • Find the shortest path (BFS) to each vertex in ascending (non descending) Order
void Unweighted( Vertex S )
{
    Enqueue(S,Q);
    while(!IsEmpty(Q)) {
        V = Dequeue(Q);
        for( V Every adjacency point of W )
            if( dist[W] == -1 ) {
                dist[W] = dist[V] + 1;
                path[W] = V;
                Enqueue(W,Q);
            }
    }
}
  • T = O(|V|+|E|)

A single source shortest path algorithm for weighted graphs

  • Negative circles are not considered

  • Find the shortest path to each vertex in ascending (non descending) Order

  • Dijkstra algorithm

    • Let s = {source point s + determine the shortest path vertex v}
    • For any vertex v not included, dist[v] is defined as the shortest path length from s to V, but the path only passes through the vertices in S. And the minimum length of path {s - > (VI ∈ s) - > V}
    • If the paths are generated in increasing order, then
      • The real shortest path must only pass through the vertex in S
      • Choose the one with the smallest dist from the vertices never included (greedy)
      • Increasing a v into S may affect the dist value of another w!
void Dijkstra( Vertex s )
{
    while(1) {
        V = Not included in vertex dist The youngest;
        if( In this way v Non-existent )
            break;
        collected[V] = true;
        for( V Every adjacency point of W )
            if( collected[W] == false )
                if( dist[V]+E<V,W> < dist[W] ){
                    dist[W] = dist[V]+E<V,W>;
                    path[W] = V;
                }
    }
}// Can't solve the problem with negative sides
  • Method 1: scan all uninvolved vertices directly - O(|V|)
    • T = O(|V|^2 + |E|) works well for dense maps
  • Method 2: store dist in the minimum heap - O(log|V|)
    • T = O(|E|log|V|) is good for sparse image

Multi source shortest path algorithm

  • Method 1: call the single source shortest path algorithm directly 𞓜 V|
    • T=O(∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣
  • Method 2: Floyd algorithm
    • T=O(∣ V ∣ 3) T=O(゗ V ゗ 3) T=O(∣ V ∣ 3) is good for dense map
  • Floyd algorithm
void Floyd()
{
    for( i=0; i<N; i++ )
        for( j=0; j<N; j++ ) {
            D[i][j] = G[i][j];
            path[i][j] = -1;
        }
    for( k=0; k<N; k++ )
        for( i=0; i<N; i++ )
            for( j=0; j<N; j++ )
                if( D[i][k]+D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k]+D[k][j];
                    path[i][j] = k;
                }
}
  • If there is a negative circle in the graph, can Floyd algorithm work? How to know if there is a negative circle in a graph?

  • You can use Floyd algorithm with simple transformation

    Negative value can be regarded as a path that cannot be repeated infinitely

    1) Check whether there is a negative value circle (check whether the weight has a negative value and find out the minimum negative value)

    2) If there is a negative circle, increase the minimum negative value + 1 for the weight of all the non diagonal elements (for example, if the minimum negative value is - 10, then the weight of all the non diagonal elements + 11), and the minimum negative value becomes 1

    3) Using Floyd algorithm

    4) Shortest path and length: directly output the shortest path saved in the matrix, and record the number of edges that the shortest path passes through n, the length is equal to the minimum negative value + 1 of the saved length minus the number of edges that the shortest path passes through

/* Single source shortest path algorithm of adjacency table store no right graph */
 
/* dist[]And path [] are all initialized to - 1 */
void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
{
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
     
    Q = CreateQueue( Graph->Nv ); /* Create an empty queue with MaxSize as an externally defined constant */
    dist[S] = 0; /* Initialize source point */
    AddQ (Q, S);
 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q);
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* For each adjacency point of V W - > adjv */
            if ( dist[W->AdjV]==-1 ) { /* If W - > adjv has not been visited */
                dist[W->AdjV] = dist[V]+1; /* W->AdjV Distance update to S */
                path[W->AdjV] = V; /* Record V on the path from S to W - > adjv */
                AddQ(Q, W->AdjV);
            }
    } /* while End*/
}
/* A single source shortest path algorithm for storage weighted graph of adjacency matrix */
 
Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* Return the smallest dist in the unrecorded vertices */
    Vertex MinV, V;
    int MinDist = INFINITY;
 
    for (V=0; V<Graph->Nv; V++) {
        if ( collected[V]==false && dist[V]<MinDist) {
            /* If V is not included and dist[V] is smaller */
            MinDist = dist[V]; /* Update minimum distance */
            MinV = V; /* Update corresponding vertex */
        }
    }
    if (MinDist < INFINITY) /* If the minimum dist is found */
        return MinV; /* Return the corresponding vertex subscript */
    else return ERROR;  /* If such a vertex does not exist, an error mark is returned */
}
 
bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;
 
    /* Initialization: the edge that does not exist in the default adjacency matrix is represented by INFINITY */
    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* First, set the starting revenue */
    dist[S] = 0;
    collected[S] = true;
 
    while (1) {
        /* V = The smallest dist in the unrecorded vertices */
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) /* If such a V does not exist */
            break;      /* Algorithm termination */
        collected[V] = true;  /* V included */
        for( W=0; W<Graph->Nv; W++ ) /* For each vertex W in the graph */
            /* If W is the adjacency of V and is not included */
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( Graph->G[V][W]<0 ) /* If there are negative edges */
                    return false; /* Unable to resolve correctly, error flag returned */
                /* If V makes dist[W] smaller */
                if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                    dist[W] = dist[V]+Graph->G[V][W]; /* Update dist[W] */
                    path[W] = V; /* Update S to W path */
                }
            }
    } /* while End*/
    return true; /* The algorithm is completed, and the correct mark is returned */
}
/* Memory multi-source shortest path algorithm of adjacency matrix */
 
bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;
 
    /* Initialization */
    for ( i=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }
 
    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]<0 ) /* If a negative circle is found */
                        return false; /* Unable to resolve correctly, error flag returned */
                    path[i][j] = k;
                }
    return true; /* The algorithm is completed, and the correct mark is returned */
}
Published 10 original articles, praised 0, visited 3
Private letter follow

Tags: network

Posted on Mon, 10 Feb 2020 22:22:39 -0800 by Garion