Here we apply a greedy algorithm to finding the shortest paths. The Problem. Graphs are often used to model networks in which one travels from one point to another. Thus, a basic algorithmic problem is to determine the shortest path between nodes in a graph. That is to say, given nodes u and v, what is the shortest u-v path? Or given a start node s, what is the shortest path from s to each other node?

We assume the problem involves a directed graph of which we know its start node s. We assume that s has a path to every other node in the same graph. Each edge in the graph has a distance greater than zero, indicating the time it takes to traverse the edge. Although we focus on directed graphs, we can handle undirected ones by just replacing every edge with two distinct edges, one from node u to node v and another from v to u.

Designing the Algorithm. Dijkstra proposed how to solve the single-source shortest-paths problem.

• Determine the length of the shortest path from s to each other node.
• Create an explored set S and add nodes with the least shortest-path distance and update the distance value.

Dijkstra's Algorithm(G,l)

Let S be the set of explored nodes 
    For each node in S, store a distance d(u)
Initially S={s} and d(s)=0
While S!=V
    Select a node not in V with at least one edge from S with the least distance
    Add node to S and update its distance
EndWhile

Detailed algorithm is on Page 138. Analyzing the algorithm. Is it always true that when Dijkstra's Algorithm adds a node v, we get the true shortest-path distance to v? This is true, and we show this by proving its correctness, showing that the paths Pu are really the shortest paths. We shall use greedy algorithm “stays ahead” to prove its correctness. Proof on Page 139. Observations about Dijkstra's algorithm.

• The algorithm does not always find shortest paths if some of the edges can have negative lengths. A more complex algorithm would be required to solve this(Bellman and Ford and to be seen when dealing with dynamic programming).
• It is simpler than described above. Can be apprehended as a physical system of pipes filled with water and nodes. A ripple-effect is seen if a water drop falls on node s. The nodes at which it reaches first are thus the shortest paths till its destination.

Implementation and running time. Thw While loop iterates n-1 times, the other part is going through all vertices and finding the minimum cost for all edges connected to them. This would take O(m) time, thus leading to an implementation that runs in O(mn) time. We can do better than this if we use the right data structures.We can improve on the efficiency by keeping the nodes not in S in a priority queue with their distances as their keys. We keep Extracting the node with the minimum key and update the keys that are still in the priority queue. We only update the distance ifit is smaller than the former distance after extracting the node with the minimum path. In summary, Using a priority queue, Dijkstra's algorithm can be implemented on a graph with n nodes and m edges to run in O(m) time, plus the time for n ExtrcatMin and m ChangeKey operations. Using the heap-based priority queue implementation discussed in Chapter 2, each priority queue operation runs in O(log n) time. Thus the overall running time would be O(m logn).

This section was a bit of a job understanding, thus I give it a scale of 8/10