CmSc 250 Intro to Algorithms

Graph Algorithms - Shortest Path

  1. Shortest paths in unweighted graphs
  2. Shortest paths in weighted graphs

    3. Animation
  3. Edsger Wybe Dijkstra

Learning Goals
Exam-like questions

  1. Shortest paths in unweighted graphs

    2. Let G(V,E) be a unweighted graph.

    Given a source vertex s, find the shortest path to all other vertices.

    The algorithm uses Breadth-first search in the graph:

    Take a vertex and examine all adjacent vertices.
    Do the same with each of the adjacent vertices

    Data structures needed:
    • A distance table with rows for each vertex w and two columns:

      1 - Distance from source vertex
      2 - Path - contains the name of the vertex that precedes w in the path from s to w.

    • A queue used to implement breadth-first search.
      It contains vertices whose distance from the source node
      has been computed and their adjacent vertices are to be examined.

    Example

    Adjacency lists :

    V1: V2, V4
    V2: V4, V5
    V3: V1, V6
    V4: V3, V5, V6, V7
    V5: V7
    V6: -
    V7: V6

    Let s = V3. The distance from V3 to V3 is 0.
    Initially the distances to all other nodes are not computed,
    and we initialize the first column in the distance table for all vertices (except V3) with -1. 

    	V1	-1	-
	V2 	-1	-
	V3 	 0	-
	V4 	-1	-
	V5 	-1	-
	V6 	-1	-
	V7 	-1	-

    Algorithm:

    1. Store s in a queue and set the distance to s to be 0 in the Distance Table.
      Initialize the distances to all other vertices as "not computed",
      e.g. using a sentinel value -1.

    2. While there are vertices in the queue:

      1. Read a vertex v from the queue
      2. For all adjacent vertices w:
        • If distance to w is -1 (not computed) do:
          • Make distance to w equal to (distance to v) + 1
          • Make path to w equal to v
          • Append w to the queue

    Complexity: O(|E| + |V|)

    We store in the queue each vertex only once (O(|V|)) - if its distance has not been computed.
    In step 2b. we examine the outgoing edges for a given vertex, thus the sum of all examined edges in the while loop will be equal to the the number of all edges - (O(|E|)).

    If we use matrix representation the complexity is O(|V|2), because we need to read an entire row in the matrix of length |V| in order to find the adjecent vertices for a given vertex.

  2. Shortest paths in weighted graphs - Dijkstra's Algorithm (proposed in 1955)

    3.

    The algorithm is similar to the algorithm for unweighted graphs.

    Differences:
    1. The adjacency lists contain in addition the weights of the edges
    2. Instead of ordinary queue, a priority queue is used (the distances being the priorities)
      and the vertex with the smallest distance is selected for processing
    3. The distance to a vertex is measured by the sum of the weights of the edges that constitute the path from the source vertex.
    4. Distances are subjected to adjustments - in case the newly computed distance is smaller.

    Algorithm:

    1. Store s in a priority queue with priority 0 and set distance to s to be 0 in the Distance Table.
      Initialize the distances to all other vertices as "not computed",
      e.g. using a sentinel value -1.

    2. While there are vertices in the queue:

      1. DeleteMin a vertex v from the queue
      2. For all adjacent vertices w do:
        • Compute new distance d= (distance to v) + weight(v,w)
        • If old distance (the distance stored in the Distance Table) is -1
          (not computed) do:
          • store new distance d in Distance Table
          • insert w in the priority queue with priority d
          • store path = v
        • If old distance > new distance d
          • Update old distance = new distance d
          • Update priority of vertex w to be d
            (this is done by updating the priority of an element in the queue - decreaseKey operation. Complexity O(log|V|))
          • Update path to w to be v

    Complexity: O(|E|log|V| + |V|log|V|) = O((|E| + |V|)log(|V|))

    Each vertex is stored only once in the queue - max elements = |V|

    The deleteMin operation is O( |V|log|V| )

    The decreaseKey operation is O(log|V|) (a search in the binary heap).
    It might be performed for each examined edge - O(|E|log|V|).

    Animation

  3. Edsger Dijkstra (1930 – 2002)

    4. Home page of Edsger Dijkstra

    Edsger Wybe Dijkstra was born in Rotterdam, Netherlands in 1930. Both of his parents were intellectual people and had received good educations. His father was a chemist, and his mother was a mathematician. In 1942, when Dijkstra was 12 years old he entered the Gymnasium Erasminium, a high school for extremely bright students, and he was educated in a number of different subjects including: Greek, Latin, French, German, English, biology, mathematics, and chemistry.

    In 1945, Dijkstra thought that he might study law and possibly serve as a representative for the Netherlandds at the United Nations. However, due to the fact that he had scored so well in chemistry, mathematics, and physics, he entered the University of Leiden, where he decided to study theoretical physics.

    He went to summer school on the subject of programming at Cambridge University, during the summer of 1951. He began part-time work at the Mathematical Centre in Amsterdam in March 1952, which further helped fuel his growing interest in programming. He finished the requirements for his theoretical physics degree as quickly as possible and began to pursue his interests in programming. One of the problems that he ran into, however was that programming still was not officially recognized as a profession. In fact, when he applied for a marriage license in 1957, he had to put down "theoretical physicist" as his profession.

    Dijkstra continued to work at the Mathematical Centre until he accepted a job as a research fellow for Burroughs Corporation, in the United States, in the early 1970s. He was awarded the ACM Turing Award in 1972. He was given the AFIPS Harry Goode Memorial Award in 1974. Dijkstra moved to Austin, Texas in the early 1980s. In 1984 he was appointed to a chair in Computer Science at the University of Texas, Austin, where he has been ever since. He is a Foreign Honorary member of the American Academy of Arts and Sciences. He is a member of the royal Netherlands Academy of Arts and Sciences. He is a Distinguished Fellow of the British Computer Society. Finally, he has a Doctor of Science Honoris Causa from Queen's University Belfast.

    Contributions to Computer Science:

    In 1956, Dijkstra came up with the "shortest-path algorithm", after he had been assigned the task of showing the powers of ARMAC, the computer that the Mathematical Centre had in it's possession; an algorithm which aids in finding the best way to travel between two points. He also used this to solve the problem of finding a way to "convey electricity to all essential circuits, while using as little expensive copper wire as possible" that the engineers that had designed the ARMAC ran into. He called it the "shortest subspanning tree algorithm." In the early 1960s, Dijkstra applied the idea of mutual exclusion to communications between a computer and its keyboard. He used the letters P and V to represent the two operations that go on in the mutual exclusion problem. This idea has become a part of pretty much all modern processors and memory board since 1964, when IBM first used it in its 360 architecture. The next problem that computer engineers must deal with that Dijkstra recognized was the "dining philosophers problem." In this problem, five philosophers are sitting at a table with a bowl of rice and a chopstick on either side of the bowl. The problem that arises is how the philosophers will be able to eat without coming to a "deadlock", ending up in a "starvation" situation, or a situation with "lack of fairness." He helped make the computer software industry a lot more disciplined by using one phrase: "GO TO considered harmful. This means that the more GO TO statements there are in a program the harder it is to follow the program's source code.

Learning Goals

  • Be able to explain the shortest path algorithms
    for weighted and unweighted graphs, and their complexity.
  • Be able to run the algorithms on paper.

Exam-like questions

  1. Explain the complexity of the shortest path algorithm for unweighted graphs.
  2. Explain the complexity of the shortest path algorithm for weighted graphs.
  3. The algorithms above were illustrated on directed graphs.
    Would there be any changes in the algorithms in case of undirected graphs?
    Would the complexity be affected?
  4. Given a weighted graph and a vertex, find the shortest paths to all other vertices
    (run the algorithm on paper)
  5. Given a unweighted graph and a vertex, find the shortest paths to all other vertices
    (run the algorithm on paper)
Back to Contents page
Created by Lydia Sinapova