HVORDAN LAVER JEG ET FLOWCHART?!!!

Hvorfor kalder du dijkstra funktionen to gange ?
Den anden gang, du kalder den, overskriver den den korteste rute.
Når du printer ruten, skal du hellere ikke kalde funktionen igen. Du burde kunne bruge den allerede beregnede værdi.

Sig til hvis du oplever andre problemer.

Jeg får denne løsning:

Antal lyskryds på ruten: 6
Den korteste rute med færrest lyskryds er: ['start', 'A', 'E', 'I', 'J', 'N', 'slut']

Her er en grafisk repræsentation af løsningen, se koden nedenunder:

Her er koden:

import heapq
import networkx as nx
import matplotlib.pyplot as plt

def dijkstra(graph, start, end):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0
    pq = [(0, start)]
    previous_vertex = {}
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        if current_distance > distance[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex]:
            distance_to_neighbor = current_distance + weight
            if distance_to_neighbor < distance[neighbor]:
                distance[neighbor] = distance_to_neighbor
                heapq.heappush(pq, (distance_to_neighbor, neighbor))
                previous_vertex[neighbor] = current_vertex
    shortest_path = []
    current_vertex = end
    while current_vertex != start:
        shortest_path.append(current_vertex)
        current_vertex = previous_vertex[current_vertex]
    shortest_path.append(start)
    shortest_path.reverse()
    return distance[end], shortest_path

def draw_graph(graph, shortest_path):
    G = nx.DiGraph()
    for vertex in graph:
        for neighbor, weight in graph[vertex]:
            G.add_edge(vertex, neighbor, weight=weight)

    pos = nx.spring_layout(G)  # positions for all nodes
    edge_labels = nx.get_edge_attributes(G, 'weight')

    # Draw the nodes and edges
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500, font_size=10, font_weight='bold')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10)

    # Highlight the shortest path
    path_edges = list(zip(shortest_path, shortest_path[1:]))
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)

    plt.show()

# Eksempel graf repræsentation
typografi = {
    'start': [('A', 5)],
    'A': [('B', 60), ('E', 20)],
    'B': [('C', 50), ('F', 5), ('A', 60)],
    'C': [('D', 40), ('B', 50)],
    'D': [('H', 30), ('C', 40)],
    'E': [('F', 40), ('I', 20), ('A', 20)],
    'F': [('G', 35), ('J', 40), ('E', 40), ('B', 5)],
    'G': [('H', 35), ('K', 15), ('F', 35)],
    'H': [('K', 20), ('D', 30), ('G', 35)],
    'I': [('J', 20), ('L', 20), ('E', 20)],
    'J': [('F', 40), ('I', 20), ('M', 40), ('N', 60)],
    'K': [('G', 15), ('H', 20), ('N', 10)],
    'L': [('I', 20), ('M', 50)],
    'M': [('L', 50), ('J', 40), ('N', 20)],
    'N': [('M', 20), ('J', 60), ('K', 10), ('slut', 5)],
    'slut': [('N', 5)]
}

startpunkt = 'start'
slutpunkt = 'slut'
korteste_afstand, korteste_rute = dijkstra(typografi, startpunkt, slutpunkt)

print("Antal lyskryds på ruten:", len(korteste_rute) - 1)
print("Den korteste rute med færrest lyskryds er:", korteste_rute)

# Tegn grafen og den korteste rute
draw_graph(typografi, korteste_rute)

Den tidligere graf var ikke tegnet proportional med længden.

Her er en version som viser længden proportional: