Graph initialisation using dictionaries for floyd algorithm on undirected graphs?

Question

I would like to know how to implement floyd on an undirected graph. With this implementation,

for k in graph:
    for i in graph:
        for j in graph:
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                pred[i][j] = pred[k][j]

I am able to get the adjacency matrix of:

   __0 __1 __2 __3 __4 

0|  0  28  38  33  63 

1|  inf  0  10  60  44 

2|  inf  inf  0  50  80 

3|  inf  inf  inf  0  30 

4|  inf  inf  inf  inf  0 

Which is a directed graph. That's fine, but I would like the adjacency matrix to display undirected graphs. From what I understand, for an undirected graph, these paths should be mirrored along the 0 diagonal, but I am not sure how to do this.

I tried:

for k in graph:
    for i in graph:
        for j in graph:
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                dist[j][i] = dist[i][k] + dist[k][j]
                pred[i][j] = pred[k][j]

But my graph turns out wrong and it looks like the algorithm is going through unneeded edges to get to the desired vertex.

   __0 __1 __2 __3 __4 

0|  0  48  38  93  63 

1|  48  0  110  60  44 

2|  38  110  0  110  80 

3|  93  60  110  0  30 

4|  63  inf  80  inf  0 

Here is the graph that I am using:

{0 : {1:28, 3:33},
1 : {2:10, 4:44},
2 : {3:50},
3 : {4:30},
4 : {}}

EDIT: Here is the full code

import ast

def floyd(graph):
    dist = {}
    pred = {} 

    for u in graph:
        dist[u] = {}
        pred[u] = {}

        for v in graph:
            dist[u][v] = float('INF')
            pred[u][v] = -1
            dist[u][u] = 0
        for z in graph[u]:
            dist[u][z] = graph[u][z]
            pred[u][z] = u

    for k in graph:
        for i in graph:
            for j in graph:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist, pred

graph = {}
graph = ast.literal_eval(open("file2.txt").read())
print graph

dist, pred = floyd(graph)

print "  ",
for j in dist: print "__" + str(j),
print "\n"
for i in dist:
        print str(i) + "|",
        for v in dist: print " %s" % (dist[i][v]),
        print "\n"

Answer 1

I think your issue can be fixed by just mirroring all the edges in your graph dictionary, like:

graph = {0 : {1:28, 3:33},
1 : {2:10, 4:44},
2 : {3:50},
3 : {4:30},
4 : {}}
# Mirror all edges
for u in graph:
    for v in graph[u]:
        if not u in graph[v]:
            graph[v][u] = graph[u][v]

That's the easiest way of setting up your input as an undirected graph (although obviously now you need to be more careful if you then edit/delete edges). When I insert this into your code, I get:

 __0__1__2__3__4

0| 0 28 38 33 63

1| 28 0 10 60 44

2| 38 10 0 50 54

3| 33 60 50 0 30

4| 63 44 54 30 0