Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    Lec-15 Dijkstra Algorithm

    Uploaded by

    Alishba Gondal
    Dijkstra's algorithm finds the shortest path between vertices in a graph. It was derived by computer scientist Edsger Dijkstra in 1956 and published in 1959. The algorithm uses a greedy approach to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. Common applications of Dijkstra's algorithm include traffic information systems, mapping, and routing systems.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Lec-15 Dijkstra Algorithm

    Uploaded by

    Alishba Gondal
    25 views18 pages
    Dijkstra's algorithm finds the shortest path between vertices in a graph. It was derived by computer scientist Edsger Dijkstra in 1956 and published in 1959. The algorithm uses a greedy approach to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. Common applications of Dijkstra's algorithm include traffic information systems, mapping, and routing systems.

    Original Title

    Lec-15 Dijkstra Algorithm.pptx

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Dijkstra's algorithm finds the shortest path between vertices in a graph. It was derived by computer scientist Edsger Dijkstra in 1956 and published in 1959. The algorithm uses a greedy approach to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. Common applications of Dijkstra's algorithm include traffic information systems, mapping, and routing systems.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    25 views18 pages

    Lec-15 Dijkstra Algorithm

    Uploaded by

    Alishba Gondal
    Dijkstra's algorithm finds the shortest path between vertices in a graph. It was derived by computer scientist Edsger Dijkstra in 1956 and published in 1959. The algorithm uses a greedy approach to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. Common applications of Dijkstra's algorithm include traffic information systems, mapping, and routing systems.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 18

    Dijkstra's Algorithm

    derived by a Dutch
    computer scientist
    ‘Edsger Wybe
    Dijkstra’ in 1956 and
    published in 1959
    Dijkstra's algorithm - is a solution to the single-source
    shortest path problem in graph theory.
    Works on both directed and undirected graphs. However, all
    edges must have nonnegative weights.
    Approach: Greedy
    Input: Weighted graph G={E,V} and source vertex, such that
    all edge weights are nonnegative
    Output: Lengths of shortest paths (or the shortest paths
    themselves) from a given source vertex to all other vertices
    This algorithm finds the with
    lowest cost (i.e. the shortest path)
    path
    between that vertex and every other
    vertex. For example, if the vertices of
    the graph represent cities and edge path
    costs represent driving distances
    between pairs of cities connected by a
    direct road, Dijkstra's algorithm can be
    used to find the shortest route between
    one city and all other cities.
    In this interconnected
    ‘Vertex’ we’ll use
    ‘Dijkstra’s Algorithm’.

    To use this algorithm


    in this network we
    have to start from a
    decided vertex and
    then continue to
    others.
    2
    2
    The simplest implementation is to store vertices in an
    Array or Linked list. This will produce a running time
    of
    O(|V|^2 + |E|)

    For graphs with very few edges and many nodes, it


    can be implemented more efficiently storing the
    graph in an adjacency list using a Binary Heap or
    Priority Queue. This will produce a running time of

    O((|E|+|V|) log |V|)


    - Traffic Information Systems are most prominent use
    - Mapping (Map Quest, Google Maps)
    - Routing Systems
    Dijkstra’s original paper:
    E. W. Dijkstra. (1959) A Note on Two Problems in
    Connection with Graphs. Numerische
    Mathematik, 1. 269-271.
    MIT OpenCourseware, 6.046J Introduction to
    Algorithms.

    You might also like