Here’s our wonderful graph from Graphspace<\/a>:![\"\"](\"https:\/\/blogs.reed.edu\/compbio\/files\/2018\/06\/Screen-Shot-2018-06-01-at-2.14.08-PM-300x232.png\")
<\/p>\n
| Start Node<\/th>\n | End Node<\/th>\n | Weight<\/th>\n<\/tr>\n |
|---|---|---|
| a<\/td>\n | b<\/td>\n | 1<\/td>\n<\/tr>\n |
| a<\/td>\n | c<\/td>\n | 1<\/td>\n<\/tr>\n |
| a<\/td>\n | e<\/td>\n | 9<\/td>\n<\/tr>\n |
| b<\/td>\n | e<\/td>\n | 3<\/td>\n<\/tr>\n |
| b<\/td>\n | c<\/td>\n | 4<\/td>\n<\/tr>\n |
| c<\/td>\n | e<\/td>\n | 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n So, using our graph, let’s find the shortest path from a to e (P_1). Looking at the graph, we can see that it is a->c->e, with cost 4. Now what we do is loop through all paths using this first path as a guide, because intuitively, there might be some obvious edges that we use in many of the shortest paths.<\/p>\n Let’s call what we’re using from P_1 the root path,\u00a0<\/strong>and call what we use when we diverge from it the\u00a0spur path.<\/strong> To find P_2 (the 2nd shortest path), we must go through the graph differently this time to make sure we just don’t get the shortest path again. Because we’re using P_1 as a guide, let’s pretend that the edge from a->c has infinite cost, so that we can never take that edge.<\/p>\n The paths that result from the root path being (a) is then [a ->b->e (4), a->e(9), a->b->c->e(7)].<\/p>\n Then, we expand our root path to be a->c,\u00a0 and pretend that the edge c->e has infinite cost, so the next path is [a->c->b->e (8)].<\/p>\n We combine the two lists of potential paths and look at their costs. [a->b->e (4), a->e(9),a->b->c->e(7), a->c->b->e(8)]. a->b->e is the 2nd shortest path (P_2)!<\/p>\n Then, we can simply search through the rest of the list for the next shortest path (P_3,…,P_k).<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" This week, we split up to delve further into the PathLinker paper according to our aims. I was assigned to research Yen’s k-shortest paths algorithm and present to the lab on Wednesday. I’m now going to attempt to explain this algorithm–bear with me. Some caveats: first, this is an algorithm for computing the k-shortest loopless … Continue reading “Yen’s k shortest paths”<\/span><\/a><\/p>\n","protected":false},"author":1725,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,11],"tags":[],"class_list":["post-279","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-summer-research-2018"],"_links":{"self":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/users\/1725"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/comments?post=279"}],"version-history":[{"count":1,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/279\/revisions"}],"predecessor-version":[{"id":281,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/279\/revisions\/281"}],"wp:attachment":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/media?parent=279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/categories?post=279"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/tags?post=279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |