graph-theorycomputer-science-theory
Regarding the Floyd-Warshall algorithm's O(n^2) storage
Why is storage 
in the Floyd-Warshall algorithm? Wouldn't it be less than that if a linked-list was used as opposed to an N by N matrix?
Solution
The worst-case size of that linked list would still be O(n^2) (I think? I'm not entirely sure I understand how you propose to use it), but the lookup cost would be sufficiently expensive to change the asymptotic complexity of the overall algorithm (operations on linked lists do not have the same complexity as operations on matrices of known size).
- Finding loops between numbers in a list of sets
- Segmenting Shortest Paths in Simple Virtual Reality Map Images
- How to find all shortest paths
- Adjacency matrix with string nodes in Python
- Polymer Simulation - Shortest route between 2 nodes, for all nodes
- Change one pair of vertices to create a cycle in an oriented graph
- Algorithms to identify all the cycle bases in a undirected graph
- How to get an ordered list of vertices defining an island/region in a heightmap array
- Construct adjacency matrix in MATLAB
- Leetcode 1372: Why do these two code snippets give different results?
- Reducing memory use in grid movement combinatorics
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Summation of nodes reachable starting from every node present in given DAG with restriction on number of childs per node
- Why finding the longest path in a graph is NP-hard
- How can I combine Group Identifiers into Single Group?
- Can the A* search algorithm be implemented without a closed list?
- Is there any algorithm to find all sub control flow graphs with single input/output in a control flow graph?
- Maximize distance while pushing crates
- Difference between vertices and edges [Graphs, Algorithm and DS]
- How to build a Minimum Spanning Tree given a list of 200 000 nodes?
- How can we be sure that paths that uses backward edges in Ford-Fulkerson are the valid ones?
- Fast way to find all connected subgraphs of given size in Python?
- Depth First Search v.s. Greedy Best First Search
- If every strongly connected component has only one incoming edge each from outside, is that necessary and sufficient for a reducible graph?
- Brent's cycle detection algorithm
- Using multi-indexing to find all combinations matching a certain pattern
- Assigning codes to nodes such that codes are unique and create two groups which share common properties
- Finding lowest common ancestor for more than two nodes
- Prove or disprove: there exists three vertexes a,b,c in a connected but incomplete graph satisfying a and b have a common neighbor c
- How to draw a node in some given coordinates