Course week 11

Self-study¶

The topics for this week are (i) Weighted graphs and their implmentation in C++, (ii) Dijkstra’s algorithm, (iii) The A-star algorithm and (iv) The efficiencies of graph search algorithms

The following links will take you to the video-lectures and the accompanying slides:

Weighted graphs and their implmentation in C++¶

video: Weighted graphs

slides C++ code

Dijkstra’s algorithm¶

video: Dijkstra (part 1)

video: Dijkstra (part 2)

video: Dijkstra (part 3)

slides

There is a mistake in section 4 of the slides used in the video. This mistake is corrected in the slides that you can download.

The A-star algorithm¶

video: A-star (part 1)

video: A-star (part 2)

slides

The efficiency of three graph algorithms¶

video: Graph algorithms’ efficiency

slides

Weighted graphs¶

Question 1

A weighted graph differs from a normal graph in that …

a weight is associated with each nodes and a node’s weight indicates how expensive it is to go through that particular node.

each edge has a weight, and the weights can be used to search for the cheapest or shortest route from some given node to some other given node.

a weighted graph must not have cycles.

each node has a weight which indicates that largest number of edges that can enter or leave that node.

Question 2

Suppose in C++ for each node \(x\) in a connected weighted graph we use the following vector to contain the adjacent nodes to \(x\) and the weight of each edge.

std::vector< std:pair<Node*,Weight>> to_neighbours;

Suppose we are accessing vector to_neighbours for node \(N\). What does a contain after the following line is executed?

auto a = to_neighbours[0].second;

zero always

a pointer to the second node adjacent to \(N\)

the weight of the edge connecting \(N\) to its first adjacent node

the number of nodes adjacent to \(N\) having zero weight

Dijkstra’s algorithm¶

The A-star algorithm¶

Question 1

Suppose we have a directed weighted graph and a starting node \(s\). Which of the following describes one way in which the A-star algorithm and Dijkstra’s algorithm differ?

A-star finds the longest path from \(s\) to some target node, whereas Dijkstra’s algorithm finds the shortest path from node \(s\) to one or more other nodes.

A-star finds the shortest path from \(s\) to one other target node. Dijkstra’s algorithm can find the shortest paths from \(s\) to all other nodes.

A-star will only work when the input graph has no cycles. Dijkstra’s algorithm does not have this restriction.

A-star solves the problem of finding the shortest path from \(s\) to one other node, even when no such path exists. Dijkstra’s algorithm will only solve this problem when a path exists.

Question 2

In the A-star algorithm something is computed that is not computed in Dijkstra’s algorithm. What is it?

A-star needs two priority queues: one where the element with the smallest priority can be extracted quickly and another where the element with the largest priority can be extracted quickly. Dijkstra’s algorithm only needs one priority queue.

A-star needs to compute an upper bound on the number of edges in the shortest path from the starting nodes to the targest node. Dijkstra’s algorithm does not need this upper bound.

A-star needs to compute a lower bound on the length of the shortest path from a given node to the target node. Dijkstra’s algorithm does not need this lower bound.

A-star needs to compute an upper bound on the length of the shortest path from a given node to the target node. Dijkstra’s algorithm does not need this upper bound.

Extra links on the topic:

A site where you can visualize the progress of different graph search algorithms

Week11 - Glossary

Submit weekly exercises¶

Questions to be submitted this week

Course week 11¶

Self-study¶

Weighted graphs and their implmentation in C++¶

Dijkstra’s algorithm¶

The A-star algorithm¶

The efficiency of three graph algorithms¶

Weighted graphs¶

Dijkstra’s algorithm¶

The A-star algorithm¶

Submit weekly exercises¶