Learn Algorithms for weighted graphs. ('Alpha' module)
Weighted and Unweighted graphs
Intro to Graphs covered unweighted graphs, where there is no weight associated with the edges of the graphs. This models real-world situations where there is no weight associated with the connections, such as a social network graph:
This module covers weighted graphs, where each edge has an associated weight or number. This number can represent many things, such as a distance between 2 locations on a map or between 2 connections on a network.
Representing a Graph
The best way to understand a graph is to draw a picture of it, but what's a good way to represent one for a computer?
Previously we used Adjacency Lists to represent a graph, but now we need to store weights as well as connections. While Adjacency Lists can be modified to store the Weight of the connections, we're going to look at a simpler method: the adjacency matrix.
An adjacency matrix is like the table that shows the distances between cities:
|Cities||Phoenix||Pittsburgh||St. Louis||Salt Lake City||San Francisco||Seattle||Washington|
|St. Louis, Mo.||1,485||600||—||1,380||2,140||2,160||840|
|Salt Lake City, Utah||650||1,900||1,380||—||750||880||2,110|
|San Francisco, Calif.||800||2,650||2,140||750||—||820||2,860|
It shows the weight or distance from each Node on the Graph to every other Node. If 2 nodes are not connected with each other, it uses 0 to mark this. Here's an adjacency matrix for a graph:
Note that the graph needs to store space for every possible connection, no matter how many there actually are. This means an adjacency matrix may not be a good choice for representing a large sparse graph, where only a small percent of possible connections are actually connected. These challenges just deal with small graphs, so the adjacency matrix is the most straightforward option to use.
Before dealing with weights, get used to the format of the graphs in the challenge below and review the previous algorithms you learned!
You're creating an app to navigate the train system and you're working on an option to find routes with the least stops. Given a graph of the train system, can you print the least number of station stops from Station 0 to all the Stations? For example, given the above graph as input, you should print out:
0 2 1 1 2 2
0 stops to station 0,
2 stops to station 1,
1 stop to station 2, etc.
The input will be in a adjacency matrix format. The first line of input will contain the number of test cases. Each test case will contain n, the number of nodes on the graph, followed by n lines for each node, with n numbers on each line for the distances to the other nodes, or 0 if there's no connection.
Output a line for each test case consisting of the number of nodes from node 0 to all the nodes. In this challenge, the actual distance does not matter, just the number of nodes between them.
1 6 0 0 1 3 0 0 0 0 0 5 0 0 1 0 0 2 1 4 3 5 2 0 7 0 0 0 1 7 0 2 0 0 4 0 2 0
0 2 1 1 2 2
A previous algorithm showed how to go through a graph one level at a time. How can you use such an algorithm to find the shortest path (by number of nodes) from one node to all the nodes?