Types of Question related to 2 Nodes of a Graph

 Existence of a Path

  • Is there a path from node AA to node BB1971. Find if Path Exists in Graph
  • Does a path satisfying certain constraints (e.g., through specific nodes or avoiding certain nodes/edges) exist? 


Distance Between Two Nodes

  • Shortest distance: Using algorithms like Dijkstra, Bellman-Ford, or BFS (for unweighted graphs).
    787. Cheapest Flights Within K Stops
  • Exact distance or range: Finding if a specific distance exists.


Number of Paths Between Two Nodes

  • Simple paths: Count paths where no node is revisited.
  • All paths: Count paths (with possible revisits).
  • K-length paths: Paths of exactly or at most kk edges

Shortest Path Between Two Nodes

  • Weight-based shortest path: Using weights on edges.
  • Fewest edges: Finding paths with the smallest number of edges.


Maximum Flow or Minimum Cut Between Two Nodes

  • Maximum flow problems deal with finding the maximum "amount" of a resource that can flow between two nodes in a capacitated graph.


Connectivity Questions

  • Are two nodes strongly/weakly connected in a directed graph?
  • Are two nodes in the same connected component?


Criticality of Nodes/Edges

  • Is a node or edge a bottleneck for connectivity or shortest path?
  • Which nodes or edges are part of all possible paths (bridges or articulation points)?


Path with Constraints

  • Find paths under specific constraints, e.g., maximum weight, passing through a set of nodes, avoiding cycles, or within a time limit.

Longest Path Between Two Nodes

  • This is NP-hard in general graphs but solvable in Directed Acyclic Graphs (DAGs).

Cycle-Related Questions

  • Does the path between two nodes form part of a cycle?
  • Can you form a cycle by connecting the two nodes?

Random Walks or Probabilistic Paths

  • Probability of reaching one node from another in a certain number of steps in a stochastic graph.


Graph Coloring or Labeling Between Nodes

  • Can the path between two nodes satisfy certain coloring rules (e.g., no adjacent nodes share the same color)?


Reachability Over Time (Dynamic Graphs)

  • If the graph changes over time (edges or nodes appear/disappear), can you still reach one node from another?

Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.