**An undirected graph**

First, I tried implementing Dijkstra's algorithm to find the shortest path from 1 to 7 for the following undirected graph:

I implemented Dijkstra's algorithm in my script dijkstra_example.py. When I run it, it gives:

distance to g7= 42.0

path= ['g1', 'g4', 'g3', 'g2', 'g7']

That is, the shortest path from 1 to 7 has length 42, and is 1->4->3->2->7.

Note: the Dijkstra's algorithm finds the shortest path, and requires that you don't have any negative edge weights.

**A directed graph**

The next thing that I wanted to do was to find the

**highest-scoring path**(longest path) through the following directed graph:

In this case the edges are directed. Apparently in numpy, to specify a directed graph, when you specify the matrix of edges, you only specify one of the edges between nodes

*i*and

*j*.

A key difference between this case and the previous one is that here I wanted the highest-scoring path, so actually this is the 'longest path problem'. Unfortunately, Dijkstra's algorithm can't be used for this. However, my husband Noel helped me find another algorithm to find the longest path in a weighted graph, see his blog post on this (thanks Noel!).

## No comments:

Post a Comment