unit.20 (3)

Unit Overview

Topics Covered:

  • Directed, Weighted Graphs

  • Graph Separation Theorem

  • Shortest Path Algorithms:

    • Dijkstra's Algorithm

    • Floyd's Algorithm

Directed, Weighted Graphs


A directed graph (or digraph) consists of a finite set of vertices (or nodes) connected by directed edges (arcs), where the edges have a direction, indicating the relationship from one vertex to another. In directed graphs, if a vertex A points to a vertex B, it does not imply that B points back to A.Weighted graphs assign a numerical value (weight) to each edge, which typically represents the cost, distance, or time required to traverse from one vertex to another. These weights allow for more complex calculations and analyses that include optimization of routes or flows within networks.

Graph Separation Theorem

Terminology:

  • Explored Region: The set of vertices that have been visited during the graph traversal, denoted by black vertices. This region contains all the nodes that have been completely processed, and their relationships explored fully.

  • Fringe: This represents the set of neighbors to the explored vertices that have not yet been visited themselves, denoted by gray vertices. The fringe serves as the frontier of the search, containing vertices that are just one edge away from the explored region.

  • Unexplored Region: The set of vertices that have not yet been visited and are outside the fringe, denoted by white vertices. These vertices are farthest from the current search efforts and remain completely untouched by the search algorithm.

Graph Search Algorithm Overview

The path search algorithm operates on the foundation of exploring vertices systematically, represented in pseudocode:

Path search(Vertex start, Vertex goal) {  
  // returns null if no path found  
  // All vertices initially marked as unexplored  
  fringe.add(start);  
  start.markAsInFringe();  
  
  for(;;) {  
    if (fringe.isEmpty()) return null;  
    Vertex v = fringe.remove();  
    v.markAsExplored();  
    for(Vertex n : v.neighbors)  
      if(n.markedAsUnexplored) {  
        fringe.add(n);  
        n.markAsInFringe();  
      }  
    if v is goal return the path to v;  
  }  
}

This algorithm successfully traverses the graph from a starting vertex to the goal vertex, employing a methodical strategy to explore each vertex and its neighbors.

Graph Separation Theorem

The Graph Separation Theorem articulates that the fringe effectively separates the explored region from the unexplored region. This means any potential path from an explored (black) vertex to an unexplored (white) vertex must necessarily traverse through an intermediary vertex in the fringe (gray), guaranteeing that all paths are sequential and logical, based upon the exploration procedure.

Proof of Theorem

  • Base Case: Initially, there are no explored vertices (black). The only vertex present is the source vertex, marked as gray (in the fringe), while all others remain unexplored (white).

  • Inductive Case: Assuming the theorem holds true for n iterations, it must be demonstrated for n+1 iterations. At each step, as new vertices are processed and marked, the separation holds true, reinforcing the theorem through logical progression.

Shortest Path Algorithms

Problem Definition

The primary aim of shortest path algorithms is to determine the shortest route(s) between specified vertices within a weighted directed or undirected graph, allowing for efficient navigation and analysis of path costs or distances.

Types of Shortest Path Problems:

  1. Single source – single goal: Finding the shortest path from one starting vertex to one specific target vertex.

  2. Single source – multiple goals: Determining the shortest paths from one source vertex to several potential goal vertices.

  3. All pairs shortest path: Identifying the shortest paths between every pair of vertices in the graph, providing comprehensive route discovery.

Assumptions

  • The graph can be directed or undirected, expanding versatility in analysis.

  • Edge weights can be zero or positive values; they do not have to represent physical distances and can embody time, cost, or other metrics.

  • Not all vertices need to be connected or reachable; some nodes may remain isolated.

  • Shortest paths are expected to be simple (without loops), although they may not be unique due to shared routes among different paths.

Dijkstra's Algorithm

Dijkstra's algorithm is specifically designed for scenarios involving a single source to multiple goals shortest path problem. It operates by prioritizing vertices based on their distance from the source vertex, utilizing a priority queue to ensure efficiency in selection of next vertices for exploration. Removal of a vertex from this queue guarantees that the route determines the minimum distance from the source to that vertex.

Execution of Dijkstra's Algorithm

The steps in Dijkstra's execution include:

  1. Initializing the fringe with the source vertex, assigned a priority of zero (as it is the starting point).

  2. For each removed vertex, the algorithm visits neighboring vertices:

    • Ignoring those that have already been visited.

    • Adding unvisited neighbors to the fringe with updated priorities based on edge weight, meaning paths can be re-evaluated as shorter paths are discovered.

    • Updating priorities whenever a newly calculated distance is less than the previously established distance.

Implementation Code

Below is an illustration of the Dijkstra's algorithm implementation:

void findSP(Vertex_ptr s) {  
  PQ<Vertex_ptr, CmpVertexPtrs> pq;  
  s->setPriority(0);  
  visit(s, pq);  
  while(!pq.empty()) {  
    Vertex_ptr v = pq.delMax();  
    v->setInFringe(false);  
    visit(v, pq);  
  }  
}
Run Time Analysis

  • Space Complexity: O(|V|), which refers to the maximum space used to store vertices in memory.

  • Time Complexity: O(|E| log |V|) in the worst-case scenario, incorporating the efficiency of operations within the priority queue as vertices and edges are processed.

Floyd's Algorithm

This algorithm is tailored to solving the all pairs shortest path problem, functioning optimally on dense graphs by employing an adjacency matrix representation. The algorithm achieves complexity of O(|V|^3), making it suitable for smaller to medium-size graphs.

Characteristics of Floyd's Algorithm

  • It is capable of accommodating graphs where edges may not exist, which are represented conceptually by infinity.

Implementation of Warshall's Algorithm

The algorithm can be implemented as follows:

for(int i=0; i<graph.size(); i++) {  
  adjMat[i][i] = true; // accounting for self-loops  
}  
for(int k=0; k<graph.size(); k++) {  
  for(int i=0; i<graph.size(); i++) {  
    if(adjMat[i][k]) {  
      for(int j=0; j<graph.size(); j++) {  
        if(adjMat[k][j]) {  
          adjMat[i][j] = true;  
        }  
      }  
    }  
  }  
}

This implementation follows a systematic approach to discover the shortest paths between every possible pair of vertices, ensuring complete route optimization in the graph.