title: How to calculate a maximum-bottleneck path with igraph?
body: <p>Given a capacity network with a single source and a single sink, how can I calculate the <a href="https://en.wikipedia.org/wiki/Widest_path_problem" rel="noreferrer">maximum-bottleneck path</a> (also known as the widest path or maximum capacity path problem) using igraph?</p>
  
  <p>I've read (e.g. <a href="http://www.cs.cmu.edu/~avrim/451f08/lectures/lect1007.pdf" rel="noreferrer">here</a> or even with pseudocode <a href="https://stackoverflow.com/questions/18552964/finding-path-with-maximum-minimum-capacity-in-graph">there</a>) that it is possible with some modifications to Dijkstra’s algorithm, but I do not want to dive into algortihm development but use igraph instead.</p>
  
  <p>Example</p>
  
  <pre class="lang-r prettyprint-override"><code>library(igraph)
  set.seed(21)
  
  nodes = cbind(
  'id' = c('Fermenters', 'Methanogens', 'carbs', 'CO2', 'H2', 'other', 'CH4', 'H2O')
  )
  
  from &lt;- c('carbs', rep('Fermenters', 3), rep('Methanogens', 2), 'CO2', 'H2')
  to &lt;- c('Fermenters', 'other', 'CO2', 'H2', 'CH4', 'H2O', rep('Methanogens', 2))
  weight &lt;- sample(1 : 20, 8)
  
  links &lt;- data.frame(from, to, weight, stringsAsFactors = FALSE)
  
  
  net = graph_from_data_frame(links, vertices = nodes, directed = T)
  
  ## Calculate max-bottleneck here !
  
  
  # # disabled because just vis
  # plot(net, edge.width = E(net)$weight)
  
  # require(networkD3)
  # require(tidyverse)
  # 
  # d3net &lt;- igraph_to_networkD3(net, group = rep(1, 8))
  # forceNetwork(
  #     Links = mutate(d3net$links, weight = E(net)$weight), Nodes = d3net$nodes,
  #     Source = 'source', Target = 'target',
  #     NodeID = 'name', Group = "group", Value = "weight", 
  #     arrows = TRUE, opacity = 1, opacityNoHover = 1
  # )
  
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/L5i2s.png" rel="noreferrer"><img src="https://i.stack.imgur.com/L5i2s.png" alt="enter image description here"></a></p>
  
  <p>So with respect to the example, how would I calculate the maximum capacity path from <code>carbs</code> to <code>H2O</code>?</p>