Weighted Graphs


Collapse Content

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.

train-LA-NYC

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?

weighted-graph

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:

CitiesPhoenix Pittsburgh St. Louis Salt Lake City San Francisco Seattle Washington
Phoenix, Ariz.2,0701,485 650 800 1,480 2,280
Pittsburgh, Pa. 2,070 600 1,900 2,650 2,520 240
St. Louis, Mo.1,485 6001,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 8808202,755
Washington, D.C. 2,280 240 840 2,110 2,8602,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?

Challenge

Print out the shortest node-distance from node 0 to all the nodes.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Contact Us
Sign in or email us at [email protected]