题目：
There are N network nodes, labelled 1 to N.Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.Note:N will be in the range [1, 100].K will be in the range [1, N].The length of times will be in the range [1, 6000].All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.
解题思路：
本题很像是树的遍历，找出离根节点最远的叶子节点。但是与树不一样的是，节点之间存在回路。如图我是构造的一组测试数据。我的想法是从根节点开始，首先找出与根节点有直通的第一层节点并将这一层所有节点入栈，同时用一个数组保存根节点与每个节点的最短延时。
1. 首先为节点定义结构体
class Node(object): def __init__(self, inx): self.inx = inx #节点序号 self.childList = [] #所有与之直连的节点列表 self.childDis = [] #到达直接节点的最小延时，下标与childList下标一致
2.遍历times，建立节点之间的直连关系
nodeList = [None for x in range(N+1)] for i in times: if nodeList[i[0]] == None: node = Node(i[0]); node.childList.append(i[1]) node.childDis.append(i[2]) nodeList[i[0]] = node #print node.inx,node.childList,node.childDis #print nodeList[i[0]].inx,nodeList[i[0]].childList,nodeList[i[0]].childDis else: nodeList[i[0]].childList.append(i[1]) nodeList[i[0]].childDis.append(i[2])
3.从K节点开始寻找最大延时节点，将过程中遍历到的节点入栈（类似广度遍历的思想），找出K能到达的所有节点，并用数组dp记录最短延时。
dp = [6001 for x in range(N+1)] dp[0] = dp[K]= 0 stack = [] stack.append(K) visit = set() visit.add(K) while len(stack) > 0: tmp = stack.pop(0) if nodeList[tmp] == None: continue for i in range(len(nodeList[tmp].childList)): if dp[nodeList[tmp].childList[i]] > nodeList[tmp].childDis[i] + dp[tmp]: #注，这里是关键一步，判断是否有更小延时路径 dp[nodeList[tmp].childList[i]] = nodeList[tmp].childDis[i] + dp[tmp] if nodeList[tmp].childList[i] not in visit: visit.add(nodeList[tmp].childList[i])
完整代码如下:
class Node(object): def __init__(self, inx): self.inx = inx self.childList = [] self.childDis = []class Solution(object): def networkDelayTime3(self, times, N, K): #build level relation nodeList = [None for x in range(N+1)] for i in times: if nodeList[i[0]] == None: node = Node(i[0]); node.childList.append(i[1]) node.childDis.append(i[2]) nodeList[i[0]] = node #print node.inx,node.childList,node.childDis #print nodeList[i[0]].inx,nodeList[i[0]].childList,nodeList[i[0]].childDis else: nodeList[i[0]].childList.append(i[1]) nodeList[i[0]].childDis.append(i[2]) dp = [6001 for x in range(N+1)] dp[0] = dp[K]= 0 stack = [] stack.append(K) visit = set() visit.add(K) while len(stack) > 0: tmp = stack.pop(0) if nodeList[tmp] == None: continue for i in range(len(nodeList[tmp].childList)): if dp[nodeList[tmp].childList[i]] > nodeList[tmp].childDis[i] + dp[tmp]: dp[nodeList[tmp].childList[i]] = nodeList[tmp].childDis[i] + dp[tmp] if nodeList[tmp].childList[i] not in visit: visit.add(nodeList[tmp].childList[i]) stack.append(nodeList[tmp].childList[i]) #print dp if 6001 in dp: return -1 else: res = dp[1] for i in range(1,len(dp)): if res < dp[i]: res = dp[i] return res