Designing an Intelligent Travel Planner with Dijkstra’s Algorithm to Boost Trip Efficiency

With the rapid development of artificial‑intelligence techniques, the tourism industry is leveraging them to improve service quality and customer experience. The article proposes an intelligent travel‑planning system that, given a network of cities and bidirectional transport links, returns for each destination the minimum travel cost and, under that cost, the maximum number of cities that can be visited.

Problem Description

The input consists of three integers n m s representing the number of cities, the number of transport links, and the start city. Each of the following m lines contains three integers u v w, indicating a bidirectional link between cities u and v with cost w. The output requires two lines: the first line lists the minimum cost from s to every city, and the second line lists, for the same minimum‑cost paths, the maximum number of cities traversed.

Algorithm Idea

The core task is to find shortest paths while preferring paths that pass through more cities when costs are equal. This can be achieved by a modified Dijkstra algorithm that maintains two arrays:

dist : the current smallest cost from the start city to each city.

city_count : the maximum number of cities visited along a shortest‑cost path to each city.

A priority queue ( pq) stores pairs (current_dist, city_id) so that the vertex with the smallest tentative distance is processed first.

Variable Initialization

dist = [float('inf')] * (n + 1)
Dist[s] = 0
city_count = [0] * (n + 1)
pq = [(0, s)]  # (distance, city)

dist

is set to infinity for all cities except the start city, whose distance is zero. city_count starts at zero because no intermediate cities have been visited yet.

Main Loop

The algorithm repeatedly extracts the city with the smallest tentative distance from pq. If the extracted distance is larger than the recorded dist for that city, the entry is ignored because a better path has already been found.

while pq:
    current_dist, u = heapq.heappop(pq)
    if current_dist > dist[u]:
        continue
    for v, w in graph[u]:
        new_dist = current_dist + w
        if new_dist < dist[v]:
            dist[v] = new_dist
            city_count[v] = city_count[u] + 1
            heapq.heappush(pq, (new_dist, v))
        elif new_dist == dist[v] and city_count[u] + 1 > city_count[v]:
            city_count[v] = city_count[u] + 1

When a strictly shorter path to v is discovered, both dist[v] and city_count[v] are updated, and the new pair is pushed onto the heap. If an equally short path is found but it traverses more cities, only city_count[v] is updated.

Result Return

return dist[1:], city_count[1:]

The function returns the arrays without the unused index 0, matching the 1‑based city numbering.

Complete Python Implementation

import heapq

def dijkstra(n, s, graph):
    dist = [float('inf')] * (n + 1)
    dist[s] = 0
    city_count = [0] * (n + 1)
    pq = [(0, s)]
    while pq:
        current_dist, u = heapq.heappop(pq)
        if current_dist > dist[u]:
            continue
        for v, w in graph[u]:
            new_dist = current_dist + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                city_count[v] = city_count[u] + 1
                heapq.heappush(pq, (new_dist, v))
            elif new_dist == dist[v] and city_count[u] + 1 > city_count[v]:
                city_count[v] = city_count[u] + 1
    return dist[1:], city_count[1:]

def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))  # undirected
    min_costs, max_cities = dijkstra(n, s, graph)
    print(' '.join(map(str, min_costs)))
    print(' '.join(map(str, max_cities)))

main()

Illustrative Walk‑through

The article follows a concrete example with n = 5 cities and the edges:

5 5 1
1 2 2
1 4 5
2 3 4
3 5 7
4 5 8

Step‑by‑step execution shows how the priority queue evolves, how dist and city_count are updated after each extraction, and how the algorithm finally yields the minimum costs 0 2 6 5 13 and the corresponding maximum city counts 0 1 2 1 3. The article includes several diagrams (preserved as

tags) that visualize the queue state and the graph after each iteration.