This is a discussion question that I just need a couple ofsentences on - no need

Question

This is a discussion question that I just need a couple ofsentences on - no need to code.

7. Based on what we have learned about graphs this week, how willyou compute all-pair shortest paths given a weighted graph? Compareit with FloydWarshall algorithm. This is a discussion question that I just need a couple ofsentences on - no need to code.

7. Based on what we have learned about graphs this week, how willyou compute all-pair shortest paths given a weighted graph? Compareit with FloydWarshall algorithm.

Explanation / Answer

Dear, It is possible to use any algorithm Bellman ford, Dijkstra,or Floyd Warshall for a given weighted graph. Dijsktra's Algorithm even though is a single-source shortest-pathsalgorithm, but for computing shortest paths for all pairs, we canrun the algorithm again and again by making each vertex source.However, there is a limitation too. As you know thatDijkstra’s single-source shortest path algorithm works if alledges weights are non-negative, so if the graph has negative edgeweights then it is not useful algorithm. Bellman ford is also a same kind of algorithm, i.e. we can applythe algorithm again and again on each vertex of the graph tocompute shortest paths between all pairs of vertices. It allowsnegative weight cycles. However, I think that Floyd Warshall algorithm is best for findingall pairs shortest paths in the graph. It allows negative edgeweights. and it has the property that we can find optimal solutionfor each vertex in a way that we compute the distance from sayvertex 1 to vertex 5, without visiting vertex 2, withought visitingvertex 3. with visiting vertex 4, 5 etc. Even though its running time is O(n^3), but for smaller graphs itis optimal.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.