En Kısa Yol Algoritmaları

package main

import "fmt"

const inf = 1 << 60

type Edge struct {
	From, To string
	Weight   int
}

func main() {
	// Gevşetmenin nasıl çalıştığını elle izleyelim
	dist := map[string]int{"A": 0, "B": inf, "C": inf, "D": inf}
	parent := map[string]string{}

	edges := []Edge{
		{"A", "B", 4},
		{"A", "C", 2},
		{"C", "B", 1},
		{"B", "D", 5},
		{"C", "D", 8},
	}

	show := func(step string) {
		fmt.Printf("%-24s", step)
		for _, n := range []string{"A", "B", "C", "D"} {
			if dist[n] >= inf {
				fmt.Printf("%6s", "∞")
				continue
			}
			fmt.Printf("%6d", dist[n])
		}
		fmt.Println()
	}

	fmt.Printf("%-24s%6s%6s%6s%6s\n", "adım", "A", "B", "C", "D")
	show("başlangıç")

	for _, e := range edges {
		if dist[e.From] >= inf {
			continue
		}
		if dist[e.From]+e.Weight < dist[e.To] {
			dist[e.To] = dist[e.From] + e.Weight
			parent[e.To] = e.From
			show(fmt.Sprintf("%s→%s (%d) gevşetildi", e.From, e.To, e.Weight))
			continue
		}
		show(fmt.Sprintf("%s→%s (%d) gevşemedi", e.From, e.To, e.Weight))
	}

	fmt.Println()
	fmt.Println("A'dan mesafeler:", dist)
	fmt.Println("ebeveynler:", parent)
	fmt.Println()
	fmt.Println("Dikkat: A→B doğrudan 4, ama A→C→B yolu 2+1=3 → daha kısa!")
	fmt.Println("Gevşetme bunu otomatik yakalar.")
}

package main

import (
	"container/heap"
	"fmt"
	"maps"
	"slices"
	"strings"
)

const inf = 1 << 60

type Edge struct {
	To     string
	Weight int
}

type Graph map[string][]Edge

func (g Graph) AddEdge(from, to string, w int) {
	g[from] = append(g[from], Edge{to, w})
	g[to] = append(g[to], Edge{from, w}) // yönsüz
	slices.SortFunc(g[from], func(a, b Edge) int { return strings.Compare(a.To, b.To) })
	slices.SortFunc(g[to], func(a, b Edge) int { return strings.Compare(a.To, b.To) })
}

func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }

// Öncelik kuyruğu: container/heap arayüzü
type item struct {
	node string
	dist int
}

type pq []item

func (q pq) Len() int { return len(q) }
func (q pq) Less(i, j int) bool {
	if q[i].dist != q[j].dist {
		return q[i].dist < q[j].dist
	}
	return q[i].node < q[j].node // deterministik
}
func (q pq) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *pq) Push(x any)   { *q = append(*q, x.(item)) }
func (q *pq) Pop() any     { old := *q; it := old[len(old)-1]; *q = old[:len(old)-1]; return it }

// dijkstra: O((V + E) log V)
func (g Graph) dijkstra(source string) (map[string]int, map[string]string) {
	dist := map[string]int{}
	parent := map[string]string{}
	for _, n := range g.Nodes() {
		dist[n] = inf
	}
	dist[source] = 0

	q := &pq{{source, 0}}
	heap.Init(q)
	done := map[string]bool{}

	for q.Len() > 0 {
		cur := heap.Pop(q).(item)
		if done[cur.node] {
			continue // eski (bayat) kayıt: atla
		}
		done[cur.node] = true

		for _, e := range g[cur.node] {
			if done[e.To] {
				continue
			}
			if newDist := dist[cur.node] + e.Weight; newDist < dist[e.To] {
				dist[e.To] = newDist
				parent[e.To] = cur.node
				heap.Push(q, item{e.To, newDist})
			}
		}
	}
	return dist, parent
}

// path: hedefe giden yolu geri kurar
func path(parent map[string]string, source, target string) ([]string, bool) {
	if source == target {
		return []string{source}, true
	}
	if _, ok := parent[target]; !ok {
		return nil, false
	}
	var out []string
	for n := target; n != ""; n = parent[n] {
		out = append(out, n)
		if n == source {
			break
		}
	}
	slices.Reverse(out)
	if out[0] != source {
		return nil, false
	}
	return out, true
}

func main() {
	// Şehirler arası mesafeler (km)
	g := Graph{}
	roads := []struct {
		a, b string
		km   int
	}{
		{"Ankara", "Konya", 258},
		{"Ankara", "Eskişehir", 233},
		{"Eskişehir", "Bursa", 154},
		{"Konya", "Antalya", 310},
		{"Eskişehir", "Afyon", 144},
		{"Afyon", "Antalya", 291},
		{"Afyon", "İzmir", 327},
		{"Bursa", "İzmir", 328},
	}
	for _, r := range roads {
		g.AddEdge(r.a, r.b, r.km)
	}
	g["Van"] = nil // bağlantısı olmayan şehir

	dist, parent := g.dijkstra("Ankara")

	fmt.Println("Ankara'dan mesafeler:")
	for _, n := range g.Nodes() {
		if dist[n] >= inf {
			fmt.Printf("  %-12s ulaşılamaz\n", n)
			continue
		}
		p, _ := path(parent, "Ankara", n)
		fmt.Printf("  %-12s %5d km  %s\n", n, dist[n], strings.Join(p, " → "))
	}

	fmt.Println()
	fmt.Println("Ankara → Antalya karşılaştırması:")
	fmt.Println("  Konya üzerinden: 258 + 310 =", 258+310, "km")
	fmt.Println("  Afyon üzerinden: 233 + 144 + 291 =", 233+144+291, "km")
	fmt.Println("  Dijkstra'nın bulduğu:", dist["Antalya"], "km")
}

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

const inf = 1 << 60

type Edge struct {
	From, To string
	Weight   int
}

type Digraph struct {
	edges []Edge
	nodes map[string]bool
}

func NewDigraph() *Digraph {
	return &Digraph{nodes: map[string]bool{}}
}

func (g *Digraph) AddEdge(from, to string, w int) {
	g.nodes[from], g.nodes[to] = true, true
	g.edges = append(g.edges, Edge{from, to, w})
}

func (g *Digraph) Nodes() []string { return slices.Sorted(maps.Keys(g.nodes)) }

// bellmanFord: negatif ağırlıkları destekler — O(V × E)
func (g *Digraph) bellmanFord(source string) (map[string]int, map[string]string, bool, []string) {
	dist := map[string]int{}
	parent := map[string]string{}
	for _, n := range g.Nodes() {
		dist[n] = inf
	}
	dist[source] = 0

	n := len(g.nodes)
	// V-1 tur: her turda tüm kenarları gevşet
	for range n - 1 {
		changed := false
		for _, e := range g.edges {
			if dist[e.From] >= inf {
				continue
			}
			if dist[e.From]+e.Weight < dist[e.To] {
				dist[e.To] = dist[e.From] + e.Weight
				parent[e.To] = e.From
				changed = true
			}
		}
		if !changed {
			break // erken çıkış: değişiklik kalmadı
		}
	}

	// V. tur: hâlâ gevşeme varsa NEGATİF DÖNGÜ var
	for _, e := range g.edges {
		if dist[e.From] >= inf {
			continue
		}
		if dist[e.From]+e.Weight < dist[e.To] {
			// Döngüyü bul: e.To'dan geriye n kez git
			cycle := findNegativeCycle(parent, e.To, n)
			return dist, parent, false, cycle
		}
	}
	return dist, parent, true, nil
}

func findNegativeCycle(parent map[string]string, start string, n int) []string {
	// Döngüye kesin girmek için n adım geri git
	node := start
	for range n {
		if p, ok := parent[node]; ok {
			node = p
		}
	}
	// Döngüyü topla
	var cycle []string
	seen := map[string]bool{}
	for cur := node; !seen[cur]; cur = parent[cur] {
		seen[cur] = true
		cycle = append(cycle, cur)
	}
	cycle = append(cycle, node)
	slices.Reverse(cycle)
	return cycle
}

func main() {
	// Negatif ağırlıklı graf (Dijkstra burada yanlış sonuç verir)
	g := NewDigraph()
	g.AddEdge("A", "B", 1)
	g.AddEdge("A", "C", 4)
	g.AddEdge("B", "C", -5)
	g.AddEdge("C", "D", 2)

	dist, parent, ok, _ := g.bellmanFord("A")
	fmt.Println("negatif ağırlıklı graf (A→B=1, A→C=4, B→C=-5, C→D=2):")
	fmt.Println("  negatif döngü yok:", ok)
	for _, n := range g.Nodes() {
		if dist[n] >= inf {
			fmt.Printf("  %s: ulaşılamaz\n", n)
			continue
		}
		fmt.Printf("  %s: %d\n", n, dist[n])
	}
	fmt.Println("  A→C: doğrudan 4 yerine A→B→C = 1-5 =", dist["C"])
	_ = parent

	// Negatif döngü
	fmt.Println()
	cyclic := NewDigraph()
	cyclic.AddEdge("A", "B", 1)
	cyclic.AddEdge("B", "C", -3)
	cyclic.AddEdge("C", "B", 1)
	cyclic.AddEdge("C", "D", 2)

	_, _, ok2, cycle := cyclic.bellmanFord("A")
	fmt.Println("negatif döngülü graf (B→C=-3, C→B=1 → toplam -2):")
	fmt.Println("  negatif döngü yok mu:", ok2)
	if !ok2 {
		fmt.Println("  bulunan döngü:", strings.Join(cycle, " → "))
		fmt.Println("  bu döngüde dolaşmak mesafeyi sonsuza kadar azaltır")
	}

	// Arbitraj tespiti: para birimi kurları
	fmt.Println()
	fmt.Println("UYGULAMA: döviz arbitrajı")
	fmt.Println("Kurların logaritmasının negatifini ağırlık yaparsan,")
	fmt.Println("negatif döngü = kâr getiren çevrim zinciri demektir.")
}

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

const inf = 1 << 40 // toplamada taşmaması için makul bir değer

type Digraph struct {
	edges map[string]map[string]int
	nodes map[string]bool
}

func NewDigraph() *Digraph {
	return &Digraph{edges: map[string]map[string]int{}, nodes: map[string]bool{}}
}

func (g *Digraph) AddEdge(from, to string, w int) {
	g.nodes[from], g.nodes[to] = true, true
	if g.edges[from] == nil {
		g.edges[from] = map[string]int{}
	}
	g.edges[from][to] = w
}

func (g *Digraph) Nodes() []string { return slices.Sorted(maps.Keys(g.nodes)) }

// floydWarshall: tüm çiftler arası en kısa yol — O(V³)
func (g *Digraph) floydWarshall() (map[string]map[string]int, map[string]map[string]string, bool) {
	nodes := g.Nodes()
	dist := map[string]map[string]int{}
	next := map[string]map[string]string{}

	for _, i := range nodes {
		dist[i] = map[string]int{}
		next[i] = map[string]string{}
		for _, j := range nodes {
			switch {
			case i == j:
				dist[i][j] = 0
			default:
				dist[i][j] = inf
			}
		}
		for to, w := range g.edges[i] {
			dist[i][to] = w
			next[i][to] = to
		}
	}

	// Üç iç içe döngü: k EN DIŞTA olmalı
	for _, k := range nodes {
		for _, i := range nodes {
			for _, j := range nodes {
				if dist[i][k] >= inf || dist[k][j] >= inf {
					continue
				}
				if through := dist[i][k] + dist[k][j]; through < dist[i][j] {
					dist[i][j] = through
					next[i][j] = next[i][k]
				}
			}
		}
	}

	// Köşegen negatifse negatif döngü var
	for _, i := range nodes {
		if dist[i][i] < 0 {
			return dist, next, false
		}
	}
	return dist, next, true
}

func reconstruct(next map[string]map[string]string, from, to string) []string {
	if next[from][to] == "" {
		return nil
	}
	path := []string{from}
	for cur := from; cur != to; cur = next[cur][to] {
		path = append(path, next[cur][to])
	}
	return path
}

func main() {
	g := NewDigraph()
	links := []struct {
		a, b string
		ms   int
	}{
		{"sunucu1", "sunucu2", 10},
		{"sunucu2", "sunucu3", 15},
		{"sunucu1", "sunucu3", 40},
		{"sunucu3", "sunucu4", 5},
		{"sunucu2", "sunucu4", 30},
		{"sunucu4", "sunucu1", 20},
	}
	for _, l := range links {
		g.AddEdge(l.a, l.b, l.ms)
	}

	dist, next, ok := g.floydWarshall()
	nodes := g.Nodes()

	fmt.Println("ağ gecikmeleri (ms):")
	for _, l := range links {
		fmt.Printf("  %s → %s: %d ms\n", l.a, l.b, l.ms)
	}

	fmt.Println()
	fmt.Println("tüm çiftler arası en kısa gecikme:")
	fmt.Printf("%-10s", "")
	for _, j := range nodes {
		fmt.Printf("%10s", j)
	}
	fmt.Println()
	for _, i := range nodes {
		fmt.Printf("%-10s", i)
		for _, j := range nodes {
			if dist[i][j] >= inf {
				fmt.Printf("%10s", "∞")
				continue
			}
			fmt.Printf("%10d", dist[i][j])
		}
		fmt.Println()
	}

	fmt.Println()
	fmt.Println("negatif döngü yok:", ok)
	fmt.Println()
	fmt.Println("örnek yollar:")
	for _, pair := range [][2]string{
		{"sunucu1", "sunucu4"},
		{"sunucu4", "sunucu3"},
		{"sunucu1", "sunucu3"},
	} {
		p := reconstruct(next, pair[0], pair[1])
		fmt.Printf("  %s → %s (%d ms): %s\n",
			pair[0], pair[1], dist[pair[0]][pair[1]], strings.Join(p, " → "))
	}

	fmt.Println()
	fmt.Println("sunucu1 → sunucu3: doğrudan 40 ms, sunucu2 üzerinden",
		10+15, "ms → Floyd-Warshall kısa olanı buldu")
}

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

const inf = 1 << 60

type Edge struct {
	To     string
	Weight int // yalnızca 0 veya 1
}

type Graph map[string][]Edge

func (g Graph) AddEdge(from, to string, w int) {
	g[from] = append(g[from], Edge{to, w})
	g[to] = append(g[to], Edge{from, w})
	slices.SortFunc(g[from], func(a, b Edge) int { return strings.Compare(a.To, b.To) })
	slices.SortFunc(g[to], func(a, b Edge) int { return strings.Compare(a.To, b.To) })
}

func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }

// zeroOneBFS: 0/1 ağırlıklı graflarda en kısa yol — O(V + E)
func (g Graph) zeroOneBFS(source string) map[string]int {
	dist := map[string]int{}
	for _, n := range g.Nodes() {
		dist[n] = inf
	}
	dist[source] = 0

	deque := []string{source}
	for len(deque) > 0 {
		cur := deque[0]
		deque = deque[1:]

		for _, e := range g[cur] {
			newDist := dist[cur] + e.Weight
			if newDist >= dist[e.To] {
				continue
			}
			dist[e.To] = newDist
			if e.Weight == 0 {
				deque = append([]string{e.To}, deque...) // 0 ağırlık: ÖNE ekle
			} else {
				deque = append(deque, e.To) // 1 ağırlık: ARKAYA ekle
			}
		}
	}
	return dist
}

func main() {
	// Labirent: bazı geçitler ücretsiz (0), bazıları kapı açmayı gerektiriyor (1)
	g := Graph{}
	passages := []struct {
		a, b string
		cost int
	}{
		{"giriş", "hol", 0},
		{"hol", "salon", 0},
		{"salon", "mutfak", 1}, // kapı
		{"hol", "koridor", 1},  // kapı
		{"koridor", "mutfak", 0},
		{"mutfak", "bahçe", 1}, // kapı
		{"salon", "balkon", 0},
	}
	for _, p := range passages {
		g.AddEdge(p.a, p.b, p.cost)
	}

	fmt.Println("geçitler (0 = açık, 1 = kapı açmak gerekir):")
	for _, p := range passages {
		fmt.Printf("  %-10s ↔ %-10s maliyet %d\n", p.a, p.b, p.cost)
	}

	dist := g.zeroOneBFS("giriş")
	fmt.Println()
	fmt.Println("girişten en az kaç kapı açarak ulaşılır:")
	for _, n := range g.Nodes() {
		if dist[n] >= inf {
			fmt.Printf("  %-10s ulaşılamaz\n", n)
			continue
		}
		fmt.Printf("  %-10s %d kapı\n", n, dist[n])
	}

	fmt.Println()
	fmt.Println("Neden çift uçlu kuyruk yeterli?")
	fmt.Println("0 ağırlıklı kenar mesafeyi artırmadığı için düğüm ÖNE eklenir;")
	fmt.Println("1 ağırlıklı kenar mesafeyi bir artırdığı için ARKAYA eklenir.")
	fmt.Println("Böylece kuyruk her zaman sıralı kalır: öncelik kuyruğuna gerek yok.")
}