I have a peculiar weighted undirected graph wherein the shortest path between a node pair, if it exists, is the same as the edge between those two nodes for majority of the node pairs (>80%). Is there an algorithm which will give me better runtime than Floyd-Warshall/Djikstra/Bellman-Ford for this type of problem?