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