Tweeted twitter.com/StackCompSci/status/689202321335693317 occurred Jan 18 '16 at 21:46 4 added 234 characters in body edited Jan 12 '16 at 11:30 ThunderWiring 15077 bronze badges Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ Length of a path is the number of edges in the path. Weight of a path is the sum of all weights of the path's edges -------- Edit: Elaborating the question: -------- Suppose there are $$x$$ different paths between $$s$$ and some $$v \in V$$. Each path has its own weight. Among those $$x$$ paths, there are $$y$$ shortest paths(pay attention $$y \subseteq x$$ and all the paths in $$y$$ have the same length). What I'm trying to find: The lightest path among the above $$y$$ paths. Also, i want to calculate that weight for every vertex in $$V$$. Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. AlthoughPay attention how $$A\rightarrow B\rightarrow D$$ and $$A \rightarrow C \rightarrow D$$ are both of length 2 Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ -------- Edit: Elaborating the question: -------- Suppose there are $$x$$ different paths between $$s$$ and some $$v \in V$$. Each path has its own weight. Among those $$x$$ paths, there are $$y$$ shortest paths(pay attention $$y \subseteq x$$ and all the paths in $$y$$ have the same length). What I'm trying to find: The lightest path among the above $$y$$ paths. Also, i want to calculate that weight for every vertex in $$V$$. Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ Length of a path is the number of edges in the path. Weight of a path is the sum of all weights of the path's edges -------- Edit: Elaborating the question: -------- Suppose there are $$x$$ different paths between $$s$$ and some $$v \in V$$. Each path has its own weight. Among those $$x$$ paths, there are $$y$$ shortest paths(pay attention $$y \subseteq x$$ and all the paths in $$y$$ have the same length). What I'm trying to find: The lightest path among the above $$y$$ paths. Also, i want to calculate that weight for every vertex in $$V$$. Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. Pay attention how $$A\rightarrow B\rightarrow D$$ and $$A \rightarrow C \rightarrow D$$ are both of length 2 Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? 3 added 443 characters in body edited Jan 11 '16 at 17:00 ThunderWiring 15077 bronze badges Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ -------- Edit: Elaborating the question: -------- Suppose there are $$x$$ different paths between $$s$$ and some $$v \in V$$. Each path has its own weight. Among those $$x$$ paths, there are $$y$$ shortest paths(pay attention $$y \subseteq x$$ and all the paths in $$y$$ have the same length). What I'm trying to find: The lightest path among the above $$y$$ paths. Also, i want to calculate that weight for every vertex in $$V$$. Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? Given a directed graph $$G = (V,E)$$ with non-negative(zero and positive) weights on the edges, and a vertex $$s \in V$$ Problem: Find the lightest path from $$s$$ to each and every vertex $$v \in V$$ and that's from the shortest paths from $$s$$ to all $$v \in V$$ -------- Edit: Elaborating the question: -------- Suppose there are $$x$$ different paths between $$s$$ and some $$v \in V$$. Each path has its own weight. Among those $$x$$ paths, there are $$y$$ shortest paths(pay attention $$y \subseteq x$$ and all the paths in $$y$$ have the same length). What I'm trying to find: The lightest path among the above $$y$$ paths. Also, i want to calculate that weight for every vertex in $$V$$. Initially, i thought about this algorithm: run BFS on $$G$$ from source $$s$$ run Dijkestra on the BFS tree from step 1 However, i ran into this problem: With source vertex $$A$$, the red path and the black path, both lead to the same vertex $$D$$. Although they are both the shortest paths from $$A$$ to $$D$$, the red path is lighter than the black one. I thought about 'tweaking' BFS: Each time i arrive at a vertex $$v$$ which i already discovered, i check whether the "new" path i already walked to $$v$$ is lighter than the one already set to $$v$$. However, i don't want to change in the algorithm, because i need to prove that it actually work from the start. How can i modify my algorithm so that the problem i pointed won't pop-out? 2 edited tags | link edited Jan 11 '16 at 9:01 Raphael♦ 58.9k2525 gold badges144144 silver badges327327 bronze badges 1 asked Jan 11 '16 at 8:37 ThunderWiring 15077 bronze badges