2024

/* 
   簡易バスダイヤ作成プログラム    c:\users\ebata\dummy1.go

   (1)バス路線があり、5つの停留所("A0", "A1", "A2", "A3", "A4", "A5")があります。
   (2)このバスは始点から運行を開始し、路線の終点でで一定時間停車した後、再び逆方向に運行を開始します。
   (3)バスは朝6時に出発して、5分単位で次の停留所で停止し、終端で10分間停止します。
   (4)これを3往復するものとします。

*/



package main

import (
	"fmt"
	"strings" // strings パッケージをインポート
	"time"
)

// バスのダイヤグラム
type BusSchedule struct {
	Route             []string             // 停留所のリスト
	DepartureTime     time.Time            // 出発時刻
	ArrivalTimeStops  map[string][]string // 各停留所の到着時刻
	ArrivalTimeRounds int                  // 往復回数
}

// バスのダイヤグラムを生成する関数
func GenerateBusSchedule(route []string, departureTime time.Time, numRoundTrips int) *BusSchedule {
	schedule := &BusSchedule{
		Route:             route,
		DepartureTime:     departureTime,
		ArrivalTimeStops:  make(map[string][]string),
		ArrivalTimeRounds: numRoundTrips,
	}

	currentTime := departureTime
	reverse := false // 逆向き運行を切り替えるフラグ

	for round := 0; round < numRoundTrips; round++ {
		routeOrder := make([]string, 0, len(route)*2-1)

		if reverse {
			// 逆向き運行の場合、終点から始点に戻る
			for i := len(route) - 1; i >= 0; i-- {
				stop := route[i]
				arrivalTime := currentTime.Format("15:04")
				schedule.ArrivalTimeStops[stop] = append(schedule.ArrivalTimeStops[stop], arrivalTime)
				routeOrder = append(routeOrder, fmt.Sprintf("%s(%d): %s", stop, len(schedule.ArrivalTimeStops[stop]), arrivalTime))
				if i > 0 {
					currentTime = currentTime.Add(5 * time.Minute)
				}
			}
			reverse = false
		} else {
			// 正向き運行の場合、始点から終点に向かう
			for i := 0; i < len(route); i++ {
				stop := route[i]
				arrivalTime := currentTime.Format("15:04")
				schedule.ArrivalTimeStops[stop] = append(schedule.ArrivalTimeStops[stop], arrivalTime)
				routeOrder = append(routeOrder, fmt.Sprintf("%s(%d): %s", stop, len(schedule.ArrivalTimeStops[stop]), arrivalTime))
				if i < len(route)-1 {
					currentTime = currentTime.Add(5 * time.Minute)
				}
			}
			reverse = true
		}

		fmt.Println(strings.Join(routeOrder, "->"))
		currentTime = currentTime.Add(10 * time.Minute) // 終点での停止時間
	}

	return schedule
}

func main() {
	route := []string{"A0", "A1", "A2", "A3", "A4", "A5"}
	departureTime := time.Date(2024, 1, 6, 6, 0, 0, 0, time.UTC)
	numRoundTrips := 3

	schedule := GenerateBusSchedule(route, departureTime, numRoundTrips)

	// routeOrder を表示
	fmt.Println("routeOrder:")
	for _, stop := range schedule.Route {
		fmt.Printf("%s:\n", stop)
		for i, arrivalTime := range schedule.ArrivalTimeStops[stop] {
			fmt.Printf("  通過%d: %s\n", i+1, arrivalTime)
		}
	}
}

出力結果

C:\Users\ebata>go run dummy1.go
A0(1): 06:00->A1(1): 06:05->A2(1): 06:10->A3(1): 06:15->A4(1): 06:20->A5(1): 06:25
A5(2): 06:35->A4(2): 06:40->A3(2): 06:45->A2(2): 06:50->A1(2): 06:55->A0(2): 07:00
A0(3): 07:10->A1(3): 07:15->A2(3): 07:20->A3(3): 07:25->A4(3): 07:30->A5(3): 07:35
routeOrder:
A0:
通過1: 06:00
通過2: 07:00
通過3: 07:10
A1:
通過1: 06:05
通過2: 06:55
通過3: 07:15
A2:
通過1: 06:10
通過2: 06:50
通過3: 07:20
A3:
通過1: 06:15
通過2: 06:45
通過3: 07:25
A4:
通過1: 06:20
通過2: 06:40
通過3: 07:30
A5:
通過1: 06:25
通過2: 06:35
通過3: 07:35

このプログラムの目的は、時刻表の乗り換え案内のアルゴリズムを実現する為のテストプログラムです。
「到着時刻より早い時間の電車やバスには乗れない」をダイクストラに組み込むことができるかを調べたものです。

ノードのValueが到着・出発時間を表わすと考えて下さい。

package main

import (
	"fmt"
	"math"
)

type Node struct {
	Name  string
	Value float64 // 各ノードに設定された数値
}

type Edge struct {
	From   *Node
	To     *Node
	Weight float64
}

func main() {
	/*
		// ノードとエッジを初期化
		nodeA := &Node{Name: "A", Value: 5}
		nodeB := &Node{Name: "B", Value: 8}
		nodeC := &Node{Name: "C", Value: 6}
		nodeD := &Node{Name: "D", Value: 2}
		nodeE := &Node{Name: "E", Value: 4}
	*/

	// ノードとエッジを初期化
	nodeA := &Node{Name: "A", Value: 1}
	nodeB := &Node{Name: "B", Value: 1}
	nodeC := &Node{Name: "C", Value: 0}
	nodeD := &Node{Name: "D", Value: 1}
	nodeE := &Node{Name: "E", Value: 1}

	/*
		edges := []Edge{
			{nodeA, nodeB, 2},
			{nodeA, nodeC, 4},
			{nodeB, nodeC, 1},
			{nodeB, nodeD, 7},
			{nodeC, nodeD, 3},
			{nodeC, nodeE, 5},
			{nodeE, nodeD, 2},
		}
	*/

	edges := []Edge{ // "方向性あり"に注意
		{nodeA, nodeB, 1},
		{nodeA, nodeC, 1},
		{nodeB, nodeC, 1},
		{nodeB, nodeD, 1},
		{nodeC, nodeD, 1},
		{nodeC, nodeE, 1},
		{nodeE, nodeD, 1},
		{nodeD, nodeE, 1},
	}

	startNode := nodeA
	targetNode := nodeE

	// ダイクストラアルゴリズムを実行
	shortestPath, totalWeight := dijkstra(startNode, targetNode, edges)

	if shortestPath == nil {
		fmt.Println("最短経路が見つかりませんでした。")
	} else {
		fmt.Printf("最短経路: %v\n", getNodeNames(shortestPath))
		fmt.Printf("最短経路の総重み: %.2f\n", totalWeight)
	}
}

func dijkstra(startNode, targetNode *Node, edges []Edge) ([]*Node, float64) {
	// ノード間の最短距離を格納するマップを初期化
	shortestDistances := make(map[*Node]float64)
	// 各ノードの前のノードを格納するマップを初期化
	predecessors := make(map[*Node]*Node)

	// 最短距離を無限大で初期化し、開始ノードの最短距離を0に設定
	for _, edge := range edges {
		shortestDistances[edge.From] = math.Inf(1)
		shortestDistances[edge.To] = math.Inf(1)
	}
	shortestDistances[startNode] = 0

	// 訪問済みのノードを格納するセットを初期化
	visitedNodes := make(map[*Node]bool)

	// まだ訪問していないノードが残っている間ループ
	for len(visitedNodes) < len(shortestDistances) {
		// 未訪問のノードの中から最短距離のノードを選択
		currentNode := getClosestUnvisitedNode(shortestDistances, visitedNodes)

		// ノードがない場合やターゲットノードに到達した場合は終了
		if currentNode == nil || currentNode == targetNode {
			break
		}

		// 隣接ノードの最短距離を更新
		for _, edge := range edges {
			//
			if edge.From == currentNode && edge.To.Value >= currentNode.Value { // ここがポイント
				distance := shortestDistances[currentNode] + edge.Weight
				if distance < shortestDistances[edge.To] {
					shortestDistances[edge.To] = distance
					predecessors[edge.To] = currentNode
				}
			}
		}

		// このノードを訪問済みとしてマーク
		visitedNodes[currentNode] = true
	}

	// 最短経路を復元
	shortestPath := make([]*Node, 0)
	currentNode := targetNode
	for currentNode != nil {
		shortestPath = append([]*Node{currentNode}, shortestPath...)
		currentNode = predecessors[currentNode]
	}

	// 最短経路の総重みを計算
	totalWeight := shortestDistances[targetNode]

	return shortestPath, totalWeight
}

func getClosestUnvisitedNode(distances map[*Node]float64, visitedNodes map[*Node]bool) *Node {
	minDistance := math.Inf(1)
	var closestNode *Node

	for node, distance := range distances {
		if !visitedNodes[node] && distance < minDistance {
			minDistance = distance
			closestNode = node
		}
	}

	return closestNode
}

func getNodeNames(nodes []*Node) []string {
	names := make([]string, len(nodes))
	for i, node := range nodes {
		names[i] = node.Name
	}
	return names
}