数据结构基础(九)

Chapter 6 Graph - Shortest Path

BFS (for unweighted shortest path)

void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S ){
  Vertex V, U;
  NodePtr ptr;

  dist[S] = 0;
  Enqueue(S, Q);
  while ( !IsEmpty(Q) ) {
    V = Dequeue( Q );
    for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) {
      U = ptr->AdjV;
      if ( dist[U] == INFINITY ) {
         dist[U] = dist[V] + 1;
         path[U] = V;
         Enqueue(U, Q);
      }
    }
  }
}

Dijkstra’s Algorithm (for weighted shortest path)

算法非常简单

void Dijkstra(Table T){
	Vertex V, W;
	for(;;){
		V = smallest unknown distance vertex;
		if(V is not a vertex){
			break;
		}
		T[V].Known = true;
		for(each W adjacent to V){
			if(T[W].Known == false){
				if(T[V].Dist + Cvw < T[W].Dist){
					Decrease(T[W].Dist to T[V].Dist + Cvw);
					T[W].Path = V;
				}
			}
		}
	}
}

$T=O(|V|)*O(\mathrm{inner\ algo.})$

Not work for negative weight edge

Different Implenentation

1. Array
   Good if the graph is dense
   $O(|V|^2+|E|)$
2. Priority Queue
   Good if the graph is sparse
   $O(|V|\log|V|+|E|\log|V|)=O(|E|\log|V|)$

SPFA (for graph with negative edge costs)

当遇到负环就无法终止

Topologic Sort (for acylic graphs / DAG)

$T=O(|E| +|V|)$ and no priority queue is needed

AOE Netwoks

See also

$EC[w]=\displaystyle\max_{(v,w)\in E}\{EC[v]+C_{v,w}\}$

$LC[v]=\displaystyle\min_{(v,w)\in E}\{LC[w]-C_{v,w}\}$

$Slave Time=LC[w]-EC[v]-C_{v,w}$

Critical Path

All-Pairs Shortest Path

Network Flow Problem