Lesson 5.3

• An algorithm is a process used to carry out a computation or solve a problem. In either hardware-based or software-based routines, algorithms function as a detailed sequence of instructions that carry out a set of operations in a likewise manner.
• Graphs are data structures used to represent "connections" between pairs of elements.
• Fill in the Blank

  A) nodes

  B) edges

  
• Nodes are represented with colored circles and edges are represented with lines that connect these circles.
• Types of Graphs

  • Undirected
  • Directed
• Undirected: if for every pair of connected nodes, you can go from one node to the other in both directions.
• Directed: if for every pair of connected nodes, you can only go from one node to another in a specific direction. We use arrows instead of simple lines to represent directed edges.
• Fill in the Blank

  A) Weight Graph

  
• With Dijkstra's Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes in the graph, producing a shortest-path tree.
• This algorithm is used in GPS devices to find the shortest path between the current location and the destination. It has broad applications in industry, specially in domains that require modeling networks.
• Dijkstra's algorithm was created and published by Dr. Edsger W. Dijkstra, a brilliant Dutch computer scientist and software engineer.
• In 1959, he published a 3-page article titled "A note on two problems in connexion with graphs" where he explained his new algorithm.
• During an interview in 2001, Dr. Dijkstra revealed how and why he designed the algorithm: What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later.
• Dijkstra's Algorithm can only work with graphs that have positive weights. This is because, during the process, the weights of the edges have to be added to find the shortest path.
• We use arrows instead of simple lines to represent directed edges.
• The weight of an edge can represent distance, time, or anything that models the "connection" between the pair of nodes it connects.
• Dijkstra's Algorithm basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
• The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
• Once the algorithm has found the shortest path between the source node and another node, that node is marked as "visited" and added to the path.
• Graphs are used to model connections between objects, people, or entities.
• They have two main elements: nodes and edges.
• Nodes represent objects and edges represent the connections between these objects
• Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph.
• This algorithm uses the weights of the edges to find the path that minimizes the total distance (weight) between the source node and all other nodes