Skip to main content Link Search Menu Expand Document (external link)

Meeting 15 Octobre 2016

Jussieu, room 26-25/105, 14:00 until 17:00

No need to bring a computer. Only paper and pen, and if needed some fruits and cookies. Coffee is provided.

We will talk about

  • survey over several important shortest path problems
  • survey over several important subset sum problems

We will solve

For a shortest path algorithm follow this decision tree

n = number of vertices, m = number of edges

  • all source-destination pairs?
    • Use Floyd-Warshall in time \(O(n^3)\) or for a sparse graph n times Dijkstra in time \(O(n^2 + m n \log n)\).
  • single source?
    • Is the graph a DAG ? Use topological sorting and then dynamic programming in time O(n+m).
    • Is the graph unweighted ? Use BFS in time O(n+m). The computed distance can be used to mark visited vertices. In that case use -1 for unvisited vertices.
    • Has the graph positive edge weights? Use Dijkstra in time O(n + m log n). Use standard priority queue. Fibonacci queues permit O(m + n log n) but are too long to implement.
    • Has the graph also negative edge weights? Use Bellman-Ford in time O(n*m)
    • Has the graph weights in {0,1}? Use Dijkstra with a double ended queue as priority queue.
    • Shortest path on a grid? Use BFS. Special care for grid border. Use matrix for marking.
    • Shortest path on a grid with doors? A door is an edge of weight 1. See {0,1} weighted graphs.
  • minimize path with maximum edge weight rather than total edge weight? Use Union-Find, adding edges in increasing weight order until source and destination are connected.
  • minimize path with maximum node weight? Sort vertices in increasing weight and then use Floyd-Warshall.
  • maximize path length over simple paths (no vertex is visited twice)?
    • Is the graph a DAG? Proceed as for shortest path.
    • Is the graph a tree? Use dynamic programming in time O(n+m).
    • Otherwise, use dynamic programming on vertex sets in time \(O(n^2 \cdot 2^n)\).
  • Has the graph node weights? Add weight on incoming arcs, and proceed as with arc weighted graphs. Or replace each vertex v by two connected vertices v+ and v-.
  • Find all edges that belong to a shortest path? Compute distances d(s,.) from source s and distances d(.,t) to destination t. The solution are exactly the edges (u,v) with d(s,u) + w(u,v) + d(v,t) = d(s,t).
  • Graph decomposable? Run Floyd-Warshall on components and topological sorting + dynamic programming on the top of the component graph.

Subset sum problems

Given positive integers x1,..,xn for a small n.

  • Find a set whose sum is equal to a target? Dynamic programming: A[k,p] = 1 of value p can be obtained by a subset of x1,..,xk. A[k,p] = A[k-1,p] or A[k-1, p - xk].
  • Find a set of sum equal a target sum where elements can be taken several times? Dynamic programming: A[k,p] = 1 of value p can be obtained by a subset of x1,..,xk. A[k,p] = A[k-1,p] or A[k, p - xk].
  • Find a set that comes closest to target sum? Search in this table A[n,.].

Given integers x1,..,xn for big n.

  • Find 2 numbers of sum equal to zero? Hash the numbers. Then for each xi search for -xi. - time O(n).
  • Find 3 numbers of sum equal to zero? Sort x. Then for each xi see if -x and x+xi intersect using linear time list merging. - time \(O(n^2)\).
  • Find k numbers of sum equal to zero? Sort x. Produce the list A of all sums over ceil(k/2) elements, together with the tuples creating the sums. Produce a similar list B for all combinations of floor(k/2) elements. Sort these lists. Look for intersection between the lists A and -B. Some work has to be done in order to ignore matching values of intersection tuples. - time could be close to \(O(n^{\lceil k/2 \rceil})\).

Links

  • here you can find booklets of the Microsoft bubble cup competition. Each contains problems and solution analysis.

Comments