{"id":113934,"date":"2021-12-02T11:40:10","date_gmt":"2021-12-02T16:40:10","guid":{"rendered":"https:\/\/ibkrcampus.com\/?p=113934"},"modified":"2022-11-21T09:49:46","modified_gmt":"2022-11-21T14:49:46","slug":"dijkstra-algorithm-part-iv","status":"publish","type":"post","link":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/","title":{"rendered":"Dijkstra Algorithm \u2013 Part IV"},"content":{"rendered":"\n

See Part I<\/a> for an overview of Dijkstra algorithm, Part II<\/a> for pseudo code of Dijkstra algorithm and Part III<\/a> for comparison with other algorithms .<\/em><\/p>\n\n\n\n

How to find the shortest path using the Dijkstra algorithm?<\/h2>\n\n\n\n

In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library. However, we are not going to install the library in our development environment, but we will copy and use the code of the two necessary classes directly in order to be able to analyse the algorithm.<\/p>\n\n\n\n

Note that the Dijkstra algorithm is implemented in other python modules as the Dijkstra from scipy.sparse.csgraph library<\/code>.<\/p>\n\n\n\n

The class \u2018DijkstraSPF\u2019 inherits from \u2018\u200b\u200bAbstractDijkstraSPF\u2019 and has two methods get_adjacent_nodes<\/code> and get_edge_weight<\/code>.<\/p>\n\n\n\n

The __init__ function<\/code> from \u2018\u200b\u200bAbstractDijkstraSPF\u2019 class has the Dijkstra algorithm as we have seen in the previous pseudocode.<\/p>\n\n\n\n

The\u00a0Graph class<\/strong>\u00a0just has two methods to deal with a graph.<\/p>\n\n\n\n

Let’s try the shortest path from A to E. As we can see, the straight path has a weight of 15, however, if we go through the nodes A-B (6), B-C(1), C-D(1) and D-E(4) that adds up to a total weight of 12, which means that this path, despite having more nodes, has a lower cost.<\/p>\n\n\n\n

\"Dijkstra<\/figure>\n\n\n\n

Example – The shortest path using the Dijkstra algorithm<\/em><\/p>\n\n\n\n

The below classes are extracted from the Dijkstra library<\/a> on GitHub.<\/p>\n\n\n\n

import math\n\nclass AbstractDijkstraSPF(object):\n\n    \"\"\" Dijkstra's shortest path algorithm, abstract class. \"\"\"\n\n    def __init__(self, G, s):\n        \"\"\" Calculate shortest path from s to other nodes in G. \"\"\"\n        self.__dist = dist = dict()\n        self.__prev = prev = dict()\n        visited = set()\n        queue = set()\n\n        dist[s] = 0\n        prev[s] = s\n        queue.add(s)\n\n        while queue:\n            u = min(queue, key=dist.get)\n            for v in self.get_adjacent_nodes(G, u):\n                if v in visited:\n                    continue\n                alt = self.get_distance(u) + self.get_edge_weight(G, u, v)\n                if alt < self.get_distance(v):\n                    dist[v] = alt\n                    prev[v] = u\n                    queue.add(v)\n            queue.remove(u)\n            visited.add(u)\n\n    @staticmethod\n    def get_adjacent_nodes(G, u):\n        raise NotImplementedError()\n\n    @staticmethod\n    def get_edge_weight(G, u, v):\n        raise NotImplementedError()\n\n    def get_distance(self, u):\n        \"\"\" Return the length of shortest path from s to u. \"\"\"\n        return self.__dist.get(u, math.inf)\n\n    def get_path(self, v):\n        \"\"\" Return the shortest path to v. \"\"\"\n        path = [v]\n        while self.__prev[v] != v:\n            v = self.__prev[v]\n            path.append(v)\n        return path[::-1]\n\nclass DijkstraSPF(AbstractDijkstraSPF):\n\n    @staticmethod\n    def get_adjacent_nodes(G, u):\n        return G.get_adjacent_nodes(u)\n\n    @staticmethod\n    def get_edge_weight(G, u, v):\n        return G.get_edge_weight(u, v)<\/code><\/pre>\n\n\n\n
Importing math.py <\/a>hosted with \u2764 by GitHub<\/a><\/code><\/pre>\n\n\n\n
.<\/p>\n\n\n\n
import random\nfrom io import StringIO\n\nclass Graph(object):\n\n    \"\"\" Directed, acyclic graph with edge weights.\n\n    Graph can be constructed two different ways. Option 1 is to create an empty\n    graph and add edges using adde<\/sub>d\u2265(u,w,v) method. For example, to\n    create graph G connecting node 0 to node 1 with edge weight 5, and node 1\n    to node 2 with edge weight 3, i.e.\n\n           5      3\n        0 ---> 1 ---> 2\n\n    >>> G = Graph()\n    >>> G.add_edge(0, 1, 5)\n    >>> G.add_edge(1, 2, 3)\n\n    Another option is to pass adjacency list and edge weights directly as\n    dictionaries. The same example with that way is constructed as:\n\n    >>> adjacency_list = {0: 1, 1: 2}\n    >>> edge_weights = {(0, 1): 5, (1, 2): 3}\n    >>> G = Graph(adjacency_list, edge_weights)\n\n    \"\"\"\n\n    def __init__(self, adjacency_list=dict(), edge_weights=dict()):\n        self.__adjacency_list = adjacency_list.copy()\n        self.__edge_weights = edge_weights.copy()\n\n    def add_edge(self, u, v, w):\n        \"\"\" Add a new edge u -> v to graph with edge weight w. \"\"\"\n        self.__edge_weights[u, v] = w\n        if u not in self.__adjacency_list:\n            self.__adjacency_list[u] = set()\n        self.__adjacency_list[u].add(v)\n\n    def get_edge_weight(self, u, v):\n        \"\"\" Get edge weight of edge between u and v. \"\"\"\n        return self.__edge_weights[u, v]\n\n    def get_adjacent_nodes(self, u):\n        \"\"\" Get nodes adjacent to u. \"\"\"\n        return self.__adjacency_list.get(u, set())\n\n    def get_number_of_nodes(self):\n        \"\"\" Return the total number of nodes in graph. \"\"\"\n        return len(self.__adjacency_list)\n\n    def get_nodes(self):\n        \"\"\" Return all nodes in this graph. \"\"\"\n        return self.__adjacency_list.keys()\n\n    def __str__(self):\n        io = StringIO()\n        N = self.get_number_of_nodes()\n        print(\"Directed, acyclic graph with %d nodes\" % N, file=io)\n        for u in self.get_nodes():\n            adj = self.get_adjacent_nodes(u)\n            print(\"Node %s: connected to %d nodes\" % (u, len(adj)), file=io)\n        return io.getvalue()<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
Importing random.py <\/a>hosted with \u2764 by GitHub<\/a><\/code><\/pre>\n\n\n\n
# If we install the dijkstra library, we can import the classes as usual.\n# from Dijkstra import DijkstraSPF, Graph\n<\/code><\/pre>\n\n\n\n
Let’s create a simple graph to test the Dijkstra shortest path algorithm.<\/p>\n\n\n\n
Let’s try the shortest path from A to E. As we can see, the direct path has a weight of 15, however, if we go through the nodes A-B (6), B-C(1), C-D(1) and D-E(4) that adds up to a total weight of 12, which means that this path, despite having more nodes, has a lower cost.<\/p>\n\n\n\n
A, B, C, D, E = nodes = list(\"ABCDE\")\n\ngraph = Graph()\ngraph.add_edge(A, B, 6)\ngraph.add_edge(A, E, 15)\ngraph.add_edge(B, C, 1)\ngraph.add_edge(C, D, 1)\ngraph.add_edge(D, E, 4)\n\ndijkstra = DijkstraSPF(graph, A)\n\nprint(\"%-5s %-5s\" % (\"label\", \"distance\"))\nfor u in nodes:\n    print(\"%-5s %8f\" % (u, dijkstra.get_distance(u)))\n\nprint(\"\\nShortest path:\")\nprint(\" -> \".join(dijkstra.get_path(E)))<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
Simple graph Dijkstra's algorithm.py <\/a>hosted with \u2764 by GitHub<\/a><\/code><\/pre>\n\n\n\n
label distance\nA     0.000000\nB     6.000000\nC     7.000000\nD     8.000000\nE     12.000000\n\nShortest path:\nA -> B -> C -> D -> E<\/code><\/pre>\n\n\n\n
If we change the weight of segment [A, E] from 15 to 10, the algorithm has a direct path to the node E.<\/p>\n\n\n\n
A, B, C, D, E = nodes = list(\"ABCDE\")\n\ngraph = Graph()\ngraph.add_edge(A, B, 6)\ngraph.add_edge(A, E, 10)\ngraph.add_edge(B, C, 1)\ngraph.add_edge(C, D, 1)\ngraph.add_edge(D, E, 4)\n\ndijkstra = DijkstraSPF(graph, A)\n\nprint(\"\\nShortest path:\")\nprint(\" -> \".join(dijkstra.get_path(E)))<\/code><\/pre>\n\n\n\n
<\/p>\n\n\n\n
Nodes list.py <\/a>hosted with \u2764 by GitHub<\/a><\/code><\/pre>\n\n\n\n
Shortest path:\nA -> E<\/code><\/pre>\n\n\n\n
As we can see, Dijkstra’s greedy algorithm is an optimal solution for finding shortest paths in a directed graph. However, it is not a valid algorithm for arbitrage since, having to normalise the prices to a logarithmic scale, we can obtain negative values for the weights. With the Dijkstra algorithm we would obtain infinite cycles, for which the Bellman-Ford algorithm is used.<\/p>\n\n\n\n
Stay tuned for the next installment in which Mario Pisa will explain why the Dijkstra algorithm fails for negative weights<\/em><\/p>\n\n\n\n
Visit QuantInsti for additional insight on this topic: https:\/\/blog.quantinsti.com\/dijkstra-algorithm\/<\/a><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.<\/p>\n","protected":false},"author":387,"featured_media":37943,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[339,343,349,338,350,341,344],"tags":[10526,865,10728,595,10726,1039,10727],"contributors-categories":[13654],"class_list":{"0":"post-113934","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-science","8":"category-programing-languages","9":"category-python-development","10":"category-ibkr-quant-news","11":"category-quant-asia-pacific","12":"category-quant-development","13":"category-quant-regions","14":"tag-dijkstra-algorithm","15":"tag-github","16":"tag-math-py","17":"tag-python","18":"tag-random-py","19":"tag-social-media-data-science","20":"tag-the-graph-class","21":"contributors-categories-quantinsti"},"pp_statuses_selecting_workflow":false,"pp_workflow_action":"current","pp_status_selection":"publish","acf":[],"yoast_head":"\nDijkstra Algorithm \u2013 Part IV | IBKR Quant<\/title>\n<meta name=\"description\" content=\"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.interactivebrokers.com\/campus\/wp-json\/wp\/v2\/posts\/113934\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Dijkstra Algorithm \u2013 Part IV | IBKR Quant Blog\" \/>\n<meta property=\"og:description\" content=\"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/\" \/>\n<meta property=\"og:site_name\" content=\"IBKR Campus US\" \/>\n<meta property=\"article:published_time\" content=\"2021-12-02T16:40:10+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-11-21T14:49:46+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"800\" \/>\n\t<meta property=\"og:image:height\" content=\"500\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Mario Pisa\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Mario Pisa\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\n\t    \"@context\": \"https:\\\/\\\/schema.org\",\n\t    \"@graph\": [\n\t        {\n\t            \"@type\": \"NewsArticle\",\n\t            \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/#article\",\n\t            \"isPartOf\": {\n\t                \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/\"\n\t            },\n\t            \"author\": {\n\t                \"name\": \"Mario Pisa\",\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#\\\/schema\\\/person\\\/f2bfe36ae4f6f088b98f90558d37ed12\"\n\t            },\n\t            \"headline\": \"Dijkstra Algorithm \u2013 Part IV\",\n\t            \"datePublished\": \"2021-12-02T16:40:10+00:00\",\n\t            \"dateModified\": \"2022-11-21T14:49:46+00:00\",\n\t            \"mainEntityOfPage\": {\n\t                \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/\"\n\t            },\n\t            \"wordCount\": 416,\n\t            \"publisher\": {\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#organization\"\n\t            },\n\t            \"image\": {\n\t                \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/#primaryimage\"\n\t            },\n\t            \"thumbnailUrl\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2020\\\/03\\\/python-colors.jpg\",\n\t            \"keywords\": [\n\t                \"Dijkstra algorithm\",\n\t                \"GitHub\",\n\t                \"math.py\",\n\t                \"Python\",\n\t                \"random.py\",\n\t                \"Social Media Data Science\",\n\t                \"the Graph class\"\n\t            ],\n\t            \"articleSection\": [\n\t                \"Data Science\",\n\t                \"Programming Languages\",\n\t                \"Python Development\",\n\t                \"Quant\",\n\t                \"Quant Asia Pacific\",\n\t                \"Quant Development\",\n\t                \"Quant Regions\"\n\t            ],\n\t            \"inLanguage\": \"en-US\"\n\t        },\n\t        {\n\t            \"@type\": \"WebPage\",\n\t            \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/\",\n\t            \"url\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/\",\n\t            \"name\": \"Dijkstra Algorithm \u2013 Part IV | IBKR Quant Blog\",\n\t            \"isPartOf\": {\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#website\"\n\t            },\n\t            \"primaryImageOfPage\": {\n\t                \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/#primaryimage\"\n\t            },\n\t            \"image\": {\n\t                \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/#primaryimage\"\n\t            },\n\t            \"thumbnailUrl\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2020\\\/03\\\/python-colors.jpg\",\n\t            \"datePublished\": \"2021-12-02T16:40:10+00:00\",\n\t            \"dateModified\": \"2022-11-21T14:49:46+00:00\",\n\t            \"description\": \"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.\",\n\t            \"inLanguage\": \"en-US\",\n\t            \"potentialAction\": [\n\t                {\n\t                    \"@type\": \"ReadAction\",\n\t                    \"target\": [\n\t                        \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/\"\n\t                    ]\n\t                }\n\t            ]\n\t        },\n\t        {\n\t            \"@type\": \"ImageObject\",\n\t            \"inLanguage\": \"en-US\",\n\t            \"@id\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/ibkr-quant-news\\\/dijkstra-algorithm-part-iv\\\/#primaryimage\",\n\t            \"url\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2020\\\/03\\\/python-colors.jpg\",\n\t            \"contentUrl\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2020\\\/03\\\/python-colors.jpg\",\n\t            \"width\": 800,\n\t            \"height\": 500,\n\t            \"caption\": \"Python\"\n\t        },\n\t        {\n\t            \"@type\": \"WebSite\",\n\t            \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#website\",\n\t            \"url\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/\",\n\t            \"name\": \"IBKR Campus US\",\n\t            \"description\": \"Financial Education from Interactive Brokers\",\n\t            \"publisher\": {\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#organization\"\n\t            },\n\t            \"potentialAction\": [\n\t                {\n\t                    \"@type\": \"SearchAction\",\n\t                    \"target\": {\n\t                        \"@type\": \"EntryPoint\",\n\t                        \"urlTemplate\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/?s={search_term_string}\"\n\t                    },\n\t                    \"query-input\": {\n\t                        \"@type\": \"PropertyValueSpecification\",\n\t                        \"valueRequired\": true,\n\t                        \"valueName\": \"search_term_string\"\n\t                    }\n\t                }\n\t            ],\n\t            \"inLanguage\": \"en-US\"\n\t        },\n\t        {\n\t            \"@type\": \"Organization\",\n\t            \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#organization\",\n\t            \"name\": \"Interactive Brokers\",\n\t            \"alternateName\": \"IBKR\",\n\t            \"url\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/\",\n\t            \"logo\": {\n\t                \"@type\": \"ImageObject\",\n\t                \"inLanguage\": \"en-US\",\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#\\\/schema\\\/logo\\\/image\\\/\",\n\t                \"url\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2024\\\/05\\\/ibkr-campus-logo.jpg\",\n\t                \"contentUrl\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/wp-content\\\/uploads\\\/sites\\\/2\\\/2024\\\/05\\\/ibkr-campus-logo.jpg\",\n\t                \"width\": 669,\n\t                \"height\": 669,\n\t                \"caption\": \"Interactive Brokers\"\n\t            },\n\t            \"image\": {\n\t                \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#\\\/schema\\\/logo\\\/image\\\/\"\n\t            },\n\t            \"publishingPrinciples\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/about-ibkr-campus\\\/\",\n\t            \"ethicsPolicy\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/cyber-security-notice\\\/\"\n\t        },\n\t        {\n\t            \"@type\": \"Person\",\n\t            \"@id\": \"https:\\\/\\\/ibkrcampus.com\\\/campus\\\/#\\\/schema\\\/person\\\/f2bfe36ae4f6f088b98f90558d37ed12\",\n\t            \"name\": \"Mario Pisa\",\n\t            \"url\": \"https:\\\/\\\/www.interactivebrokers.com\\\/campus\\\/author\\\/mariopisa\\\/\"\n\t        }\n\t    ]\n\t}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Dijkstra Algorithm \u2013 Part IV | IBKR Quant","description":"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.interactivebrokers.com\/campus\/wp-json\/wp\/v2\/posts\/113934\/","og_locale":"en_US","og_type":"article","og_title":"Dijkstra Algorithm \u2013 Part IV | IBKR Quant Blog","og_description":"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.","og_url":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/","og_site_name":"IBKR Campus US","article_published_time":"2021-12-02T16:40:10+00:00","article_modified_time":"2022-11-21T14:49:46+00:00","og_image":[{"width":800,"height":500,"url":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","type":"image\/jpeg"}],"author":"Mario Pisa","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Mario Pisa","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"NewsArticle","@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/#article","isPartOf":{"@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/"},"author":{"name":"Mario Pisa","@id":"https:\/\/ibkrcampus.com\/campus\/#\/schema\/person\/f2bfe36ae4f6f088b98f90558d37ed12"},"headline":"Dijkstra Algorithm \u2013 Part IV","datePublished":"2021-12-02T16:40:10+00:00","dateModified":"2022-11-21T14:49:46+00:00","mainEntityOfPage":{"@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/"},"wordCount":416,"publisher":{"@id":"https:\/\/ibkrcampus.com\/campus\/#organization"},"image":{"@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/#primaryimage"},"thumbnailUrl":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","keywords":["Dijkstra algorithm","GitHub","math.py","Python","random.py","Social Media Data Science","the Graph class"],"articleSection":["Data Science","Programming Languages","Python Development","Quant","Quant Asia Pacific","Quant Development","Quant Regions"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/","url":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/","name":"Dijkstra Algorithm \u2013 Part IV | IBKR Quant Blog","isPartOf":{"@id":"https:\/\/ibkrcampus.com\/campus\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/#primaryimage"},"image":{"@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/#primaryimage"},"thumbnailUrl":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","datePublished":"2021-12-02T16:40:10+00:00","dateModified":"2022-11-21T14:49:46+00:00","description":"In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library.","inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.interactivebrokers.com\/campus\/ibkr-quant-news\/dijkstra-algorithm-part-iv\/#primaryimage","url":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","contentUrl":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","width":800,"height":500,"caption":"Python"},{"@type":"WebSite","@id":"https:\/\/ibkrcampus.com\/campus\/#website","url":"https:\/\/ibkrcampus.com\/campus\/","name":"IBKR Campus US","description":"Financial Education from Interactive Brokers","publisher":{"@id":"https:\/\/ibkrcampus.com\/campus\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/ibkrcampus.com\/campus\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/ibkrcampus.com\/campus\/#organization","name":"Interactive Brokers","alternateName":"IBKR","url":"https:\/\/ibkrcampus.com\/campus\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/ibkrcampus.com\/campus\/#\/schema\/logo\/image\/","url":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2024\/05\/ibkr-campus-logo.jpg","contentUrl":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2024\/05\/ibkr-campus-logo.jpg","width":669,"height":669,"caption":"Interactive Brokers"},"image":{"@id":"https:\/\/ibkrcampus.com\/campus\/#\/schema\/logo\/image\/"},"publishingPrinciples":"https:\/\/www.interactivebrokers.com\/campus\/about-ibkr-campus\/","ethicsPolicy":"https:\/\/www.interactivebrokers.com\/campus\/cyber-security-notice\/"},{"@type":"Person","@id":"https:\/\/ibkrcampus.com\/campus\/#\/schema\/person\/f2bfe36ae4f6f088b98f90558d37ed12","name":"Mario Pisa","url":"https:\/\/www.interactivebrokers.com\/campus\/author\/mariopisa\/"}]}},"jetpack_featured_media_url":"https:\/\/www.interactivebrokers.com\/campus\/wp-content\/uploads\/sites\/2\/2020\/03\/python-colors.jpg","_links":{"self":[{"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/posts\/113934","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/users\/387"}],"replies":[{"embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/comments?post=113934"}],"version-history":[{"count":0,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/posts\/113934\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/media\/37943"}],"wp:attachment":[{"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/media?parent=113934"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/categories?post=113934"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/tags?post=113934"},{"taxonomy":"contributors-categories","embeddable":true,"href":"https:\/\/ibkrcampus.com\/campus\/wp-json\/wp\/v2\/contributors-categories?post=113934"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}