• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Dec 12th, 2018 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <queue>
2. #include <algorithm>
3. #include <string>
4. #include <list>
5.
6. /**
7.  * Returns an std::list of vertex keys that creates some shortest path between `start` and `end`.
8.  *
9.  * This list MUST include the key of the `start` vertex as the first vertex in the list, the key of
10.  * the `end` vertex as the last element in the list, and an ordered list of all vertexMap that must
11.  * be traveled along the shortest path.
12.  *
13.  * For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".
14.  *
15.  * @param start The key for the starting vertex.
16.  * @param end   The key for the ending vertex.
17.  */
18. template <class V, class E>
19. std::list<std::string> Graph<V,E>::shortestPath(const std::string start, const std::string end) {
20.   struct Vertex {
21.     std::string key;
22.     int length;
23.
24.     Vertex() {
25.       key = "";
26.       length = 0;
27.     }
28.
29.     Vertex(std::string theKey, int theLength) {
30.       key = theKey;
31.       length = theLength;
32.     }
33.   };
34.
35.
36.   std::list<std::string> path;
37.   std::queue<string> q;
38.   q.push(start);
39.
40.   std::unordered_map<std::string, Vertex> vertexMap;
41.   vertexMap.insert(make_pair(start, Vertex()));
42.
43.   while (!q.empty()) {
44.     std::string & key = q.front();
45.     q.pop();
46.
47.     Vertex vertex = vertexMap.at(key);
48.     std::list<reference_wrapper<E>> edges = incidentEdges(key);
49.
50.     for (typename std::list<reference_wrapper<E>>::iterator it = edges.begin(); it != edges.end(); it++) {
51.       Edge edge = (*it).get();
52.       std::string edgeKey;
53.
54.       if (edge.dest().key() != key) {
55.         edgeKey = edge.dest().key();
56.       } else {
57.         edgeKey = edge.source().key();
58.       }
59.
60.       bool shouldClear = false;
61.
62.       if (vertexMap.find(edgeKey) == vertexMap.end()) {
63.         q.push(edgeKey);
64.         vertexMap.insert(make_pair(edgeKey, Vertex(key, 1 + vertex.length)));
65.
66.         shouldClear = true;
67.       }
68.
69.       if (shouldClear && end == edgeKey) {
70.         while (!q.empty()) {
71.           q.pop();
72.         }
73.
74.         break;
75.       }
76.     }
77.   }
78.
79.   std::string current = end;
80.
81.   while (current.length() != 0) {
82.     path.push_front(current);
83.     current = vertexMap.at(current).key;
84.   }
85.
86.   return path;
87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top
{"ft_lang_label":"__label__en","ft_lang_prob":0.5979993,"math_prob":0.91684246,"size":2295,"snap":"2019-26-2019-30","text_gpt3_token_len":638,"char_repetition_ratio":0.16019206,"word_repetition_ratio":0.010416667,"special_character_ratio":0.34945533,"punctuation_ratio":0.2803532,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99241006,"pos_list":[0,1,2,3,4,5,6,7,8,9,10],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-18T11:57:25Z\",\"WARC-Record-ID\":\"<urn:uuid:1016c48d-04a0-4f6f-99ba-7f6141f15ec6>\",\"Content-Length\":\"26360\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ea075b30-ab32-481e-9239-c5337e60c1a8>\",\"WARC-Concurrent-To\":\"<urn:uuid:5a9367f8-2535-4d09-9788-ffcb6709dd10>\",\"WARC-IP-Address\":\"104.20.209.21\",\"WARC-Target-URI\":\"https://pastebin.com/Q8nbzZYX\",\"WARC-Payload-Digest\":\"sha1:M67DPHH7R2YM5AQNNOCKEYFF5H5RHHMP\",\"WARC-Block-Digest\":\"sha1:OP2OFOQQVKMPG2UPNE22J4FP6LH73F22\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195525627.38_warc_CC-MAIN-20190718104512-20190718130512-00226.warc.gz\"}"}