Python 최 단 경로 문 제 를 실현 하 는 방법
시작 하기 전에 우 리 는 먼저 그림 을 만 들 고 인접 행렬 을 사용 하여 방향 망 을 표시 합 니 다.
class Graph(object):
"""
"""
def __init__(self, kind):
# : , , ,
# kind: Undigraph, Digraph, Undinetwork, Dinetwork,
self.kind = kind
#
self.vertexs = []
# , ,
self.arcs = []
#
self.vexnum = 0
# ( )
self.arcnum = 0
def CreateGraph(self, vertex_list, edge_list):
"""
:param vertex_list:
:param edge_list:
:return:
"""
self.vexnum = len(vertex_list)
self.arcnum = len(edge_list)
for vertex in vertex_list:
vertex = Vertex(vertex)
#
self.vertexs.append(vertex)
# ,
self.arcs.append([float('inf')] * self.vexnum)
for edge in edge_list:
ivertex = self.LocateVertex(edge[0])
jvertex = self.LocateVertex(edge[1])
weight = edge[2]
self.InsertArc(ivertex, jvertex, weight)
def LocateVertex(self, vertex):
"""
:param vertex:
:return:
"""
index = 0
while index < self.vexnum:
if self.vertexs[index].data == vertex:
return index
else:
index += 1
def InsertArc(self, ivertex, jvertex, weight):
"""
:param ivertex:
:param jvertex:
:param weight:
:return:
"""
if self.kind == 'Dinetwork':
self.arcs[ivertex][jvertex] = weight
Vertex()의 정 의 는 참고 할 수 있 습 니 다이 블 로그여 기 는 해당 하 는 코드 를 붙 이지 않 습 니 다.2.문제 의 출처
만약 내 가 도시 A A A 에서 출발 하여 기 차 를 타고 다른 도시 로 여행 을 간다 면 어떻게 노선 을 계획 하여 소비 하 는 차표 값 을 가장 적 게 합 니까?상기 그림 에서 도 시 를 네트워크 의 정점 으로 보고 두 도시 간 에 필요 한 차표 값 을 대응 호의 가중치 로 본다 면 이 문제 의 본질은 두 정점 간 의 가중치 가 가장 작은 경 로 를 구 하 는 것 이다.최 단 경로(S h o r t e s t(Shortest P a t h)Path 라 고 부른다.
3.Dijkstra 알고리즘
D i j k s t r a Dijkstra Dijkstra 알고리즘 은 중국어 이름 은 디 제 스 트 라 알고리즘 으로 원점 에서 나머지 정점 까지 의 가장 짧 은 경 로 를 찾 는 데 자주 사용 된다.
가령 G={V,{A}}G=\{V,\{A\}\}G={V,{A}}은 n n 개의 정점 을 포함 하 는 유방 향 망 으로 이 그림 의 정점 v v v 를 원점 으로 D i j k s t r a 를 사용한다
Dijkstra Dijkstra 알고리즘 은 정점 v v v 에서 그림 의 나머지 각 정점 의 가장 짧 은 경 로 를 구 하 는 기본 적 인 사고방식 은 다음 과 같다.
(1)집합 S S 를 사용 하여 가장 짧 은 경로 의 종점 을 기록 합 니 다.초기 에는 S={v}S=\{v\}S={v};
(2)길이 가 가장 짧 은 경 로 를 선택 하 십시오.이 경로 의 종점 w*8712°V-S w\in V-S w*8712°V-S 는 w w 를 S S S S 에 합병 하고 이 최 단 경로 의 길 이 를 D w D 로 기록 합 니 다.w Dw；
(3)V−S V-S V−S 중 임의의 정점 s s 에 대해 원점 에서 정점 s s s 까지 의 최 단 경로 길 이 를 D s D 로 기록한다.s Ds,그리고 정점 w 에서 정점 s s s 까지 의 호의 가중치 를 D w s D {로 기록 합 니 다.ws}Dws,D w+D w s
D i j k s t r a Dijkstra Dijkstra 알고리즘 은 P r i m Prim Prim 알고리즘 의 그림자 가 있 습 니 다.여 기 는 보조 목록 을 사용 합 니 다
Dist원점 에서 모든 종점 까지 의 최 단 경로 길 이 를 저장 하고 목록Path모든 최 단 경로 에서 마지막 두 번 째 정점 의 아래 표(아크 꼬리 아래 표)를 저장 합 니 다.그 밖 에 정점 이 가장 짧 은 경 로 를 구 했 는 지 기록 하기 위해 서 는 목록 이 필요 합 니 다flag다음은 D i j k s t r a Dijkstra Dijkstra 알고리즘 을 결합 하여 위의 방향 망 을 분석 해 보 겠 습 니 다.
(1)여기 서 해 야 할 일 은 리스트 를 업데이트 하 는 것 입 니 다
Dist리스트Path정점 A A 를 시작 으로 S S S 에 먼저 넣 은 다음 에 정점 A A 를 호미 로 하 는 가장 짧 은 경 로 를 찾 습 니 다.여기 서 정점 B B B 를 찾 은 다음 에 다음 정점 을 계속 찾 습 니 다.이 럴 때 판단 을 해 야 합 니 다.즉,D w+D w sD i j k s t r a Dijkstra Dijkstra 알고리즘 코드 는 다음 과 같 습 니 다.
def Dijkstra(self, Vertex):
"""
Dijkstra , Vertex
:param Vertex:
:return:
"""
#
Dist = []
# ( )
Path = []
#
flag = [False] * self.vexnum
index = 0
while index < self.vexnum:
Dist.append(self.arcs[Vertex][index])
if self.arcs[Vertex][index] < float('inf'):
#
Path.append(Vertex)
else:
Path.append(-1)
index += 1
# Vertex
Dist[Vertex] = 0
Path[Vertex] = 0
flag[Vertex] = True
index = 1
while index < self.vexnum:
minDist = float('inf')
# wVertex
for i in range(self.vexnum):
if not flag[i] and Dist[i] < minDist:
wVertex = i
minDist = Dist[i]
flag[wVertex] = True
sVertex = 0
minDist = float('inf')
# sVertex
while sVertex < self.vexnum:
if not flag[sVertex]:
if self.arcs[wVertex][sVertex] < minDist and \
Dist[wVertex] + self.arcs[wVertex][sVertex] < Dist[sVertex]:
#
Dist[sVertex] = Dist[wVertex] + self.arcs[wVertex][sVertex]
Path[sVertex] = wVertex
sVertex += 1
index += 1
#
self.ShortestPathDijkstra(Vertex, Dist, Path)
def ShortestPathDijkstra(self, Vertex, Dist, Path):
"""
Vertex
:param Vertex:
:param Dist:
:param Path:
:return:
"""
tPath = []
index = 0
while index < self.vexnum:
# index
if index != Vertex:
print(' ' + self.vertexs[Vertex].data + ' ' + self.vertexs[index].data + ' :')
# Vertex index
tPath.append(index)
former = Path[index]
while former != Vertex:
tPath.append(former)
former = Path[former]
tPath.append(Vertex)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[index])
index += 1
F l o y d Floyd Floyd 알고리즘 은 중국어 이름 은 프로 이 드 알고리즘 으로 모든 정점 간 의 가장 짧 은 경 로 를 푸 는 데 자주 사 용 됩 니 다.
가령 G={V,{A}}G=\{V,\{A\}\}G={V,{A}}}은 n n 개의 정점 을 포함 하 는 유방 향 망 으로 F l o y d Floyd Floyd 알고리즘 을 사용 하여 그림 의 각 정점 간 의 가장 짧 은 경 로 를 구 하 는 기본 적 인 사고방식 은 다음 과 같다.
(1)그림 G G G 에서 두 개의 정점 v v v v 와 w w w 에 대해 정점 v v v 와 정점 w w 의 최 단 경로 길 이 를 D v w D {로 기록 합 니 다.vw}Dvw,그리고 나머지 각 정점 이 이 두 정점 간 의 가장 짧 은 경로 의 정점 인지 순서대로 판단 합 니 다.정점 v v v 와 정점 w w 를 제외 한 임의의 정점 u u u 에 대해 서 는 정점 v v v 와 정점 u u 의 최 단 경로 길 이 를 D v u D {로 기록 합 니 다.vu}Dvu,그리고 정점 u u 와 정점 w w 의 최 단 경로 길 이 는 D u w D {로 기 록 됩 니 다.U}Duw,만약 D v u+D u w
물론 모든 정점 에 D i j k s t r a Dijkstra Dijkstra 알고리즘 을 사용 하여 모든 정점 의 가장 짧 은 경 로 를 구 할 수 있 습 니 다.F l o y d Floyd Floyd 알고리즘 에 대해 서 는 보조 2 차원 배열 을 사용 합 니 다
Dist원점 에서 각 정점 간 의 최 단 경로 길 이 를 저장 하고 2 차원 배열Path각 최 단 경로 에서 마지막 두 번 째 정점 의 아래 표(아크 꼬리 아래 표)를 저장 합 니 다.다음은 F l o y d Floyd Floyd 알고리즘 을 결합 하여 맨 위 에 있 는 방향 망 을 분석 해 보 겠 습 니 다(정점 이 많 기 때문에 여 기 는 A-I A-I A-I 의 가장 짧 은 경 로 를 선택 하여 설명 합 니 다). F l o y d Floyd Floyd 알고리즘 코드 는 다음 과 같 습 니 다.
def Floyd(self):
"""
Floyd ,
:return:
"""
Dist = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
Path = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
for row in range(self.vexnum):
for column in range(self.vexnum):
Dist[row][column] = self.arcs[row][column]
if self.arcs[row][column] < float('inf') and row != column:
Path[row][column] = row
else:
Path[row][column] = -1
# uVertex
for uVertex in range(self.vexnum):
for vVertex in range(self.vexnum):
for wVertex in range(self.vexnum):
if vVertex != wVertex and \
Dist[vVertex][uVertex] + Dist[uVertex][wVertex] < Dist[vVertex][wVertex]:
Dist[vVertex][wVertex] = Dist[vVertex][uVertex] + Dist[uVertex][wVertex]
Path[vVertex][wVertex] = Path[uVertex][wVertex]
#
self.ShortestPathFloyd(Dist, Path)
def ShortestPathFloyd(self, Dist, Path):
"""
:param Dist:
:param Path:
:return:
"""
tPath = []
for start in range(self.vexnum):
for end in range(self.vexnum):
if start != end and Dist[start][end] < float('inf'):
print(' ' + self.vertexs[start].data + ' ' + self.vertexs[end].data +
' :')
tVertex = Path[start][end]
tPath.append(end)
while tVertex != -1 and tVertex != start:
tPath.append(tVertex)
tVertex = Path[start][tVertex]
tPath.append(start)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[start][end])
테스트 코드 는 다음 과 같 습 니 다:
if __name__ == '__main__':
graph = Graph(kind='Dinetwork')
graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'],
edge_list=[('A', 'B', 4), ('A', 'C', 8), ('B', 'C', 3), ('B', 'D', 8),
('C', 'E', 1), ('C', 'F', 6), ('D', 'G', 7), ('D', 'H', 4),
('E', 'D', 2), ('E', 'F', 6), ('F', 'H', 2), ('G', 'I', 9),
('H', 'G', 14), ('H', 'I', 10)])
print('{:*^30}'.format('Dijkstra '))
# index 0
graph.Dijkstra(0)
print('{:*^30}'.format('Floyd '))
graph.Floyd()
여기 서 한 가지 만 보 았 습 니 다.바로 정점 A A 에서 정점 I I I I 까지 의 경 로 를 볼 수 있 습 니 다.D i j k s t r a Dijkstra Dijkstra 알고리즘 과 F l o y d Floyd Floyd 알고리즘 이 구 하 는 가장 짧 은 경 로 는 모두 24 입 니 다.
파 이 썬 이 가장 짧 은 경 로 를 실현 하 는 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 파 이 썬 의 가장 짧 은 경로 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
