As I know one of ways for storing a weighted graph is using Adjacency List but cons of this solution is when we want to get weight of a pair vertex this will cost O(n) by looping the adjacency vertex.
So I have a solution to improve that by using Map<NodeID, Map<NodeID, Weight>> then when we want to get weight of a pair vertex, for example (1, 2) we just call Node[1].get(Node[2]), this only cost O(1).
Is this correct? I'm using Java so can it have a risk?
Does map in Java work at O(1)? I think it works at O(logN^2)
Depends to what type of map. HashMap can bring about O(1)
It's usually O(1) and in the worst case is O(n) if you use HashMap
store graph in two ways at the same time 1- Adjacency List for algorithms like dfs and bfs
2- map of pair<int,int> to get cost of an edge in O(log m) time
You can sort the adjacency lists for all vertices and then use binary search to achieve O(logN) worst-case :)