Weighted Graphs

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.

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
Phoenix, Ariz.	—	2,070	1,485	650	800	1,480	2,280
Pittsburgh, Pa.	2,070	—	600	1,900	2,650	2,520	240
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
Seattle, Wash.	1,480	2,520	2,160	880	820	—	2,755
Washington, D.C.	2,280	240	840	2,110	2,860	2,755	—

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!

Challenge

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

There are 0 stops to station 0, 2 stops to station 1, 1 stop to station 2, etc.

Input/Output Format

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.

Sample Input/Output

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

Guideline

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?