Как получить и сохранить результаты "для" l oop в виде списка после запуска алгоритма Дейкстры? - PullRequest
Новая
       62

Как получить и сохранить результаты "для" l oop в виде списка после запуска алгоритма Дейкстры?

0 голосов
/ 26 мая 2020

Я пытаюсь решить проблему с помощью алгоритма Дейкстры. По сути, я хочу случайным образом выбрать начальный и конечный узлы и найти расстояния по каждому пути после объединения узлов и запуска алгоритма. Наконец, я хочу сохранить результат в виде списка. Пока код работает хорошо, однако у меня возникла проблема с сохранением результата в виде списка. Вот код, который я использовал. 

import random
from random import seed
from random import random
from random import randint
import pandas as pd
import numpy as np
import statistics 

distance = [(0,7,3,0,0),(7,0,1,2,6),(3,1,0,2,0),(0,2,2,0,4),(0,6,0,4,0)]
dist = np.array(distance)
graph = dist

# Python program for Dijkstra's  

from collections import defaultdict 
class Graph:   
    def minDistance(self,dist,queue): 
        minimum = float("Inf") 
        min_index = -1
        for i in range(len(dist)): 
            if dist[i] < minimum and i in queue: 
                minimum = dist[i] 
                min_index = i 
        return min_index  
    def printPath(self, parent, end): 
        if parent[end] == -1 :  
            #print (end), 
            return
        self.printPath(parent , parent[end]) 
        #print (end),     
    def printSolution(self, dist, parent): 
        #print("Vertex and Path \t\tDistance from Source") 
        #print((start, end, dist[end])), self.printPath(parent,end)  #if you want to see start and end nodes

        print(dist[end]), self.printPath(parent,end)  #if you do not want to see start and end nodes

    '''Function that implements Dijkstra's single source shortest path 
    algorithm for a graph represented using adjacency matrix 
    representation'''
    def dijkstra(self, graph, start): 
        row = len(graph) 
        col = len(graph[0]) 
        dist = [float("Inf")] * row 
        parent = [-1] * row 
        dist[start] = 0
        queue = [] 
        for i in range(row): 
            queue.append(i) 
        while queue: 
            u = self.minDistance(dist,queue)  
            queue.remove(u) 
            for i in range(col): 
                '''Update dist[i] only if it is in queue, there is 
                an edge from u to i, and total weight of path from 
                start to i through u is smaller than current value of 
                dist[i]'''
                if graph[u][i] and i in queue: 
                    if dist[u] + graph[u][i] < dist[i]: 
                        dist[i] = dist[u] + graph[u][i] 
                        parent[i] = u   
        self.printSolution(dist,parent)   
g= Graph() 

seed(1)
start1 = []
for x in range(3):
    start = randint(0, 3)
    start1.append(start)

seed(3)
end1 = []
for x in range(3):
    end = randint(2,4)
    end1.append(end)

start = start1
end = end1

results = []
for i in start1:
    for q in end1:
        start = i
        end = q
        if i != q:
            results.append(g.dijkstra(graph,i))

Приведенный выше код дает такой результат ... 

1
6
6
3
9
9
6
6

Когда я вызываю сохраненный список, я получаю значения "none". 

results

[None, None, None, None, None, None, None, None]

I wi sh, чтобы получить следующие результаты: 

[1,6,6,3,9,9,6,6,]

Поскольку я новичок в использовании python, Буду безмерно благодарен, если кто-нибудь поможет мне сохранить результат в виде списка.

1 Ответ

0 голосов
/ 29 мая 2020

в results вы добавляете возвращаемое значение из g.dijkstra(graph,i). И b / c команды возврата нет, она возвращает None. Следовательно, вы добавляете только None. Добавьте return some-value в конце dijkstra(), и все должно работать.

...