Longest path between any pair of vertices

def DFS(graph, src, prev_len,

max_len, visited):

visited[src] = 1

curr_len = 0

adjacent = None

for i in range(len(graph[src])):

adjacent = graph[src][i]

if (not visited[adjacent[0]]):

curr_len = prev_len + adjacent[1]

DFS(graph, adjacent[0], curr_len,

max_len, visited)

if (max_len[0] < curr_len):

max_len[0] = curr_len

curr_len = 0

def longestCable(graph, n):

max_len = [-999999999999]

for i in range(1, n + 1):

visited = [False] * (n + 1)

DFS(graph, i, 0, max_len, visited)

return max_len[0]

if __name__ == '__main__':

n = 6

graph = [[] for i in range(n + 1)]

graph[1].append([2, 3])

graph[2].append([1, 3])

graph[2].append([3, 4])

graph[3].append([2, 4])

graph[2].append([6, 2])

graph[6].append([2, 2])

graph[4].append([6, 6])

graph[6].append([4, 6])

graph[5].append([6, 5])

graph[6].append([5, 5])

print("Maximum length of cable =",

longestCable(graph, n))

Dijkstra’s shortest path algorithm

import sys

class Graph():

def __init__(self, vertices):

self.V = vertices

self.graph = [[0 for column in range(vertices)]

for row in range(vertices)]

def printSolution(self, dist):

print("Vertex \tDistance from Source")

for node in range(self.V):

print(node, "\t", dist[node])

def minDistance(self, dist, sptSet):

min = sys.maxsize

for u in range(self.V):

if dist[u] < min and sptSet[u] == False:

min = dist[u]

min_index = u

return min_index

def dijkstra(self, src):

dist = [sys.maxsize] * self.V

dist[src] = 0

sptSet = [False] * self.V

for cout in range(self.V):

x = self.minDistance(dist, sptSet)

sptSet[x] = True

for y in range(self.V):

if self.graph[x][y] > 0 and sptSet[y] == False and \

dist[y] > dist[x] + self.graph[x][y]:

dist[y] = dist[x] + self.graph[x][y]

self.printSolution(dist)

g = Graph(9)

g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

[4, 0, 8, 0, 0, 0, 0, 11, 0],

[0, 8, 0, 7, 0, 4, 0, 0, 2],

[0, 0, 7, 0, 9, 14, 0, 0, 0],

[0, 0, 0, 9, 0, 10, 0, 0, 0],

[0, 0, 4, 14, 10, 0, 2, 0, 0],

[0, 0, 0, 0, 0, 2, 0, 1, 6],

[8, 11, 0, 0, 0, 0, 1, 0, 7],

[0, 0, 2, 0, 0, 0, 6, 7, 0]

];

g.dijkstra(0);