# Expanding Dijkstra to accommodate MaxFlow (Simple)

 Andrew Butcher · December 2, 2015 I am new to this site, I apologise if this is in the wrong place or the format or something else is wrong.I am looking to extend the following code to accommodate Ford-Fulkerson's Max Flow, but I am not sure where to begin. The code needs to use the existing code as a base, so that both algorithms are in the same Python.To clarify A>D in the separate Path file is path for Dijkstra when the code is executed.I hope this makes sense. I am new to Python, but eager to learn.The code needs to do the following:--- AIMS ---Read in a file called “network.txt” – a multi-line file with node, nearest neighbour and distance metric informationRead in a file called “path.txt” – a single line file with start and destination information, where the line is of the form “A>D” (any start / end combination is possible)Print out to the screen every path discovered during the calculation, along with its associated bottleneck flow valueThen print out the total max flow for the network--- Network.txt ---0,2,4,1,6,0,0 2,0,0,0,5,0,0 4,0,0,0,0,5,0 1,0,0,0,1,1,0 6,5,0,1,0,5,5 0,0,5,1,5,0,0 0,0,0,0,5,0,0--- Path.txt ---A>D---- DIJKSTRA CODE STARTS HERE ----``infinity = 1000000invalid_node = -1class Node:    previous = invalid_node    distanceFromSource = infinity    visited = Falsedef populateNetworkTable():    # array containing array of values for each line    network = []    networkFile = open("network.txt", "r")    numberOfNodes = 0    # reading network.txt file a line at a time     for line in networkFile:        # increment nodeCount        numberOfNodes += 1        network.append(map(int, line.strip().split(',')))    return networkdef populateNodeTable():    # array containing nodeTable visited/unvisited,prevNode and distFromSrc    nodeTable = []     i = 0    for i in range(len(network)):        nodeTable.append(Node())    # set distFromSource of startNode to 0    nodeTable[startNode].distanceFromSource = 0    nodeTable[startNode].visited = True    return nodeTable# go through all distances of unvisited, find the one with lowest distdef setNewCurrentNode(nodeTable):    nextNode = -1       nodeIndex = 0    nextDistance = infinity    for node in nodeTable:        if node.visited == False and node.distanceFromSource < nextDistance:            nextNode = nodeIndex            nextDistance = node.distanceFromSource        nodeIndex+=1    return nextNode# the following finds each of the neighbours of current nodedef findNeighbour(currentNode):    # find nearest neighbour of currentNode    currentRow = network[currentNode]    currentNeighbours = []    i = 0    for distance in currentRow:        #get back the index number / position if distance = 0        if distance != 0:            #save the location            currentNeighbours.append(i)        i += 1        return currentNeighbours def readRoute():     routeFile = open("route.txt", "r")    for line in routeFile:        nodes = line.split(">")        startNode = nodes[0]        endNode = nodes[1]    startNode =(ord(startNode) - 65)     endNode =(ord(endNode) - 65)    return startNode, endNodedef calculateRoute(nodeTable,currentNode,startNode):    route = []    while True:        route.append(currentNode)        if currentNode == startNode:            break        currentNode = nodeTable[currentNode].previous    route.reverse()    route = "".join(chr(node+65) for node in route)    return route# go through nodeTable and add distance and previous if unvisited def calculateTentativeDistance(nodeTable,currentNeighbours):    for neighbour in currentNeighbours:        if nodeTable[neighbour].visited == True:            pass        else:            # calculate tentative distances            newDistance = nodeTable[currentNode].distanceFromSource + network[currentNode][neighbour]            if (nodeTable[neighbour].distanceFromSource > newDistance):                 nodeTable[neighbour].distanceFromSource = newDistance                 nodeTable[neighbour].previous = currentNode    return nodeTabledef calculateMaxFlow()#create network tablenetwork = populateNetworkTable()#get startNode and endNode from filestartNode, endNode = readRoute()# set currentNode to startNodecurrentNode = startNode# create Node tablenodeTable = populateNodeTable()# continue until desination reachedwhile currentNode != endNode:    # get list of current neighbours    currentNeighbours = findNeighbour(currentNode)    # set current node as visited    nodeTable[currentNode].visited = True    # get new nodeTable    nodeTable = calculateTentativeDistance(nodeTable,currentNeighbours)    # set new current node    currentNode = setNewCurrentNode(nodeTable)    # get the route solution    route = calculateRoute(nodeTable,currentNode, startNode)print("The shortest route is: " + route)print("The tentative distance is: " + str(nodeTable[currentNode].distanceFromSource))``

## Replies

Nothing to see here.

## Python

124,674 followers